poj2942Knights of the Round Table

代码敲的迷迷糊糊的照把书上的给搬上来的
给篇讲的不错的解题报告各种定义都有 http://blog.csdn.net/lyy289065406/article/details/6756821
做这题之前一定要把相关定义搞清楚割点双连通分量二分图奇圈
View Code
  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 #include<stack>
  7 #include<vector>
  8 using namespace std;
  9 struct node
 10 {
 11     int u,v;
 12 };
 13 vector<int>G[1010],bcc[1010];
 14 int w[1010][1010],pre[1010],iscut[1010],bccno[1010],dc,bc,odd[1010],co[1010];
 15 stack<node>s;
 16 int dfs(int u,int fa)
 17 {
 18     int lowu  = pre[u]= ++dc;
 19     int child  =0,i;
 20     for(i = 0 ; i < G[u].size() ; i++)
 21     {
 22         int v = G[u][i];
 23         node e = (node){u,v};
 24         if(!pre[v])
 25         {
 26             s.push(e);
 27             child++;
 28             int lowv = dfs(v,u);
 29             lowu = min(lowv,lowu);
 30             if(lowv>=pre[u])
 31             {
 32                 bc++;
 33                 bcc[bc].clear();//将找到的双连通分量依次 存起来
 34                 iscut[u] = 1;
 35                 for(;;)
 36                 {
 37                     node x = s.top();
 38                     s.pop();
 39                     if(bccno[x.u]!=bc)
 40                     {
 41                         bcc[bc].push_back(x.u);
 42                         bccno[x.u] = bc;
 43                     }
 44                     if(bccno[x.v]!=bc)
 45                     {
 46                         bcc[bc].push_back(x.v);
 47                         bccno[x.v] = bc;
 48                     }
 49                     if(x.u==u&&x.v==v)
 50                         break;
 51                 }
 52             }
 53         }
 54         else if(pre[v]<pre[u]&&v!=fa)
 55         {
 56             s.push(e);
 57             lowu = min(lowu,pre[v]);
 58         }
 59     }
 60     if(fa<0&&child==1)
 61         iscut[u] = 0;//其实没看出来iscut有嘛用。。
 62     return lowu;
 63 }
 64 void find_bcc(int n)//找双连通分量
 65 {
 66     memset(pre,0,sizeof(pre));
 67     memset(iscut,0,sizeof(iscut));
 68     memset(bccno,0,sizeof(bccno));
 69     dc = bc = 0;
 70     for(int i = 1 ; i <= n ; i++)
 71         if(!pre[i])
 72             dfs(i,-1);
 73 }
 74 int bipart(int u,int b)//判断是不是二分图 着色法
 75 {
 76     int i;
 77     for(i = 0 ; i < G[u].size() ; i++)
 78     {
 79         int v = G[u][i];
 80         if(bccno[v]!=b) continue;
 81         if(co[v] == co[u])
 82         return 0;
 83         if(!co[v])
 84         {
 85             co[v] = 3-co[u];
 86             if(!bipart(v,b))
 87             return 0;
 88         }
 89     }
 90     return 1;
 91 }
 92 int main()
 93 {
 94     int i,j,k,n,m,g;
 95     while(cin>>n>>m)
 96     {
 97         if(n==0&&m==0)
 98             break;
 99         for(i = 1; i <= n ; i++)
100             G[i].clear();
101         memset(w,0,sizeof(w));
102         for(i = 1 ; i <= m ;i++)
103         {
104             int u,v;
105             scanf("%d%d",&u,&v);
106             w[u][v] = 1;
107             w[v][u] = 1;
108         }
109         for(i = 1; i <= n ; i++)
110             for(j = i+1 ; j <= n ; j++)
111                 if(!w[i][j])
112                 {
113                     G[i].push_back(j);
114                     G[j].push_back(i);
115                 }
116         find_bcc(n);
117         memset(odd,0,sizeof(odd));
118         for(i = 1 ; i <= bc ; i++)
119         {
120             memset(co,0,sizeof(co));
121             for(j = 0 ; j < bcc[i].size() ; j++)
122             bccno[bcc[i][j]] = i;//双连通分量的割顶
123             int u = bcc[i][0];
124             co[u] = 1;
125             if(!bipart(u,i))
126             {
127                 for(g =  0 ; g < bcc[i].size() ;g++)
128                 odd[bcc[i][g]] = 1;
129             }
130         }
131         int ans = 0;
132         for(i = 1 ; i <= n ; i++)//不在奇圈中的计数
133             if(!odd[i])
134             ans++;
135         cout<<ans<<endl;
136     }
137     return 0;
138 }