[POJ2942 Knights of the Round Table]【点的双连通分量】

【题目大意】
给一个无向图，对于每个点，求他是否在一个奇环中。如果不是ans++。输出ans。
【算法分析】
先求点的双连通分量，然后对于每个双连通分量，如果他里面有奇环，那么整个双连通分量上的点都在某奇环上。（这个可以用可以用奇偶性证明，实际上就是把整个图搞成两个有重叠部分的环）
然后判断一个双连通分量里有无奇环就可以交替染色。如果出现一条边的两端颜色相等，那么有奇环。
否则无奇环（利用反证法证明）
【其它】
原来我一直用的那个自创的沙茶并查集类Tarjan思想的算的是边的双连通分量，而不是点的双连通分量。于是果断WA到沙茶。。。哎，算法问题。。。
然后终于下定决心学习正版的Tarjan。学习结束重写1Y。
【CODE】
#include #include #include #define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define clr(T) memset(T,0,sizeof(T))
const int N=1005;
struct edge{int x,y,next;}g[N*N];
int n,m,times,tot,e,Qt,cnt,check;
int a[N][N],ls[N],vis[N];
int DFN[N],done[N],Stack[N*N],low[N],Q[N*N],color[N*N],odd[N];

inline void addedge(int x,int y){
g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e;
color[e]=0;
}

void init(){
int i,j,x,y;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
a[i][j]=i!=j;
for (i=1;i<=m;i++){
scanf("%d%d",&x,&y);
a[x][y]=a[y][x]=0;
}
times=tot=cnt=0;
e=1;
clr(ls);
clr(vis);
clr(DFN);
clr(done);
clr(low);
clr(odd);
for (i=1;i for (j=i+1;j<=n;j++)
if (a[i][j]){
addedge(i,j);
addedge(j,i);
}
}

void draw(int x){
vis[x]=cnt;
for (int t=ls[x];t;t=g[t].next)
if (color[t]==cnt && vis[g[t].y]!=cnt){
odd[g[t].y]=1-odd[x];
draw(g[t].y);
}else
if (color[t]==cnt && vis[g[t].y]==cnt && odd[g[t].y]==odd[x])
check=1;
}

void solve(int x){
cnt++;
for (int i=1;i<=Qt;i++){
color[Q[i]]=cnt;
color[Q[i]^1]=cnt;
}
check=0;
odd[x]=1;
draw(x);
if (check)
for (int i=1;i<=Qt;i++)
done[g[Q[i]].x]=done[g[Q[i]].y]=1;
}

void dfs(int x,int fa){
DFN[x]=low[x]=++times;
for (int t=ls[x];t;t=g[t].next){
int y=g[t].y;
if (y==fa) continue;
if (!DFN[y]){
Stack[++tot]=t;
dfs(y,x);
low[x]=min(low[x],low[y]);
if (DFN[x]<=low[y]){
Qt=0;
while (Stack[tot]!=t)
Q[++Qt]=Stack[tot–];
Q[++Qt]=Stack[tot–];
solve(x);
}
}else if (DFN[y] Stack[++tot]=t;
low[x]=min(low[x],DFN[y]);
}
}
}

void Tarjan(){
for (int i=1;i<=n;i++)
if (!DFN[i])
dfs(i,0);
}

int main(){
for (;;){
scanf("%d%d",&n,&m);
if (!n) break;
init();
Tarjan();
int ans=0;
for (int i=1;i<=n;i++)
if (!done[i]) ans++;
printf("%dn",ans);
}
return 0;
}