【二分图判定】hdu3478 Catch

详细的题解：http://www.docin.com/p-517243379.html

一个图是二分图等价于其至少有两个节点且没有奇环。

二分图判定的方法：从任意点出发进行一次dfs黑白染色，若某个点之前已经访问过(vis[v]==1)且color[v]==color[u]，则存在奇环。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 using namespace std;
 5 #define N 100001
 6 vector<int>G[N];
 7 typedef vector<int>::iterator ITER;
 8 int T,n,m,S,vis[N];
 9 bool col[N];
10 int x,y;
11 bool dfs(int U,bool now)
12 {
13     vis[U]=1;
14     for(ITER it=G[U].begin();it!=G[U].end();it++)
15       if(!vis[*it])
16         {
17           col[*it]=(now^1);
18           if(!dfs(*it,now^1)) return 0;
19         }
20       else if(col[*it]==col[U]) return 0;
21     return 1;
22 }
23 int main()
24 {
25     scanf("%d",&T);
26     for(int q=1;q<=T;q++)
27       {
28         printf("Case %d: ",q);
29         memset(vis,0,sizeof(vis));
30         scanf("%d%d%d",&n,&m,&S); S++;
31         for(int i=1;i<=m;i++)
32           {
33             scanf("%d%d",&x,&y);
34             G[x+1].push_back(y+1);
35             G[y+1].push_back(x+1);
36           }
37         if(!dfs(S,col[S])) puts("YES");
38         else puts("NO");
39         if(q==T) break;
40         for(int i=1;i<=n;i++) G[i].clear();
41       }
42     return 0;
43 }