灰书例题，用染色判断二分图在点双联通分量找奇圈。
写错了几次，返祖边不能入栈。
======
题目建模利用补图，因为是圆桌，所以人在奇环上。
其实返祖边可以入栈，我自己没判(DFN[i]<DFN[u])才萎掉的。
======
再梳理一下。
首先在有向图中Tarjan向下（if(!DFN[i]){）是从树边走，向上更新Low是沿着后向边（else{Low[u]=min(DFN[i],Low[u]);}，前向边(DFN[i]<DFN[u])是要排除的。
我在else里一开始写了入栈和更新Low没排除前向边就错了。但是索性去掉入栈就AC了，是因为先前向边一定不会更新Low数组，（DFN[i]>DFN[u]>Low[u]）。
想想应该还是把那个判断(DFN[i]<DFN[u])写上比较好。
Code
#include <iostream>
#include <cstring>
#include <vector>
#include <stack>
#define PII make_pair
using namespace std;
const int maxn=1000+10,maxm=1000000+10;
bool G[maxn][maxn],ok[maxn];
int n,m,DFN[maxn],Low[maxn],belong[maxn],Index,cnt;
vector<int> BCC[maxn];
stack< pair<int,int> > s;
void Tarjan(int u,int fa)
{
DFN[u]=Low[u]=++Index;
for(int i=1;i<=n;i++)
if(i!=fa && G[u][i] && i!=u){
if(!DFN[i]){
s.push(PII(u,i));
Tarjan(i,u);
Low[u]=min(Low[i],Low[u]);
if(DFN[u]<=Low[i]){
BCC[++cnt].clear();
pair<int,int> e;
do{
e=s.top();s.pop();
if(belong[e.first ]!=cnt){belong[e.first ]=cnt;BCC[cnt].push_back(e.first );}
if(belong[e.second]!=cnt){belong[e.second]=cnt;BCC[cnt].push_back(e.second);}
}while((e.first!=u)||(e.second!=i));
}
}
else Low[u]=min(DFN[i],Low[u]);
}
}
bool color(int u)
{
for(int i=1;i<=n;i++){
if((!G[u][i])||(belong[u]!=belong[i])||(i==u))continue;
if(DFN[i]==DFN[u])return 0;
if(!DFN[i]){
DFN[i]=3-DFN[u];
if(!color(i))return 0;
}
}
return 1;
}
int main()
{
ios::sync_with_stdio(0);
while(cin>>n>>m){
if(n==0 && m==0)break;
memset(G,1,sizeof(G));
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
G[x][y]=G[y][x]=0;
}
memset(ok,0,sizeof(ok));
memset(DFN,0,sizeof(DFN));
memset(Low,0,sizeof(Low));
memset(belong,0,sizeof(belong));
Index=0;cnt=0;
for(int i=1;i<=n;i++)
if(!DFN[i])
Tarjan(i,0);
for(int i=1;i<=cnt;i++){
memset(DFN,0,sizeof(DFN));
for(int j=0;j<BCC[i].size();j++)
belong[BCC[i][j]]=i;
DFN[BCC[i][0]]=1;
if(!color(BCC[i][0]))
for(int j=0;j<BCC[i].size();j++)ok[BCC[i][j]]=1;
}
int ans=0;
for(int i=1;i<=n;i++)ans+=ok[i];
cout<<n-ans<<endl;
}
return 0;
}
一个萎掉的例子，处理一条返祖边祖先节点时会把一个已经在某一个BCC里孩子加到当前BCC，就是说只要返祖边向上的方向，不能要返祖边向下的方向。
Code
6 8
1 4
1 5
1 6
2 4
2 5
2 6
3 6
4 5
//WA
try1->2
push1,2
try2->3
push2,3
try3->1
push3,1
try3->4
push3,4
try4->6
push4,6
try6->5
push6,5
try5->3
push5,3
pop5,3
pop6,5
pop4,6
pop3,4
try3->5
push3,5
pop3,5
pop3,1
pop2,3
pop1,2
try1->3
push1,3
belong:1,5
belong:1,3
belong:1,6
belong:1,4
belong:2,3
belong:2,5
belong:2,1
belong:2,2
2
//AC
try1->2
push1,2
try2->3
push2,3
try3->1
push3,1
try3->4
push3,4
try4->6
push4,6
try6->5
push6,5
try5->3
push5,3
pop5,3
pop6,5
pop4,6
pop3,4
try3->5
pop3,1
pop2,3
pop1,2
try1->3
belong:1,5
belong:1,3
belong:1,6
belong:1,4
belong:2,3
belong:2,1
belong:2,2
3
