poj2942 Knights of the Round Table 双连通分支 tarjan

题解：http://blog.csdn.net/lyy289065406/article/details/6756821
讲的很详细我就不多说了。
代码（完全白书上的）
  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <stdlib.h>
  6 #include <vector>
  7 #include <queue>
  8 #include <stack>
  9 #define loop(s,i,n) for(i = s;i < n;i++)
 10 #define cl(a,b) memset(a,b,sizeof(a))
 11 const int maxn = 1005;
 12 using namespace std;
 13 int pre[maxn],iscut[maxn],bccno[maxn],dfsclock,bcc_cnt;
 14 vector<int>g[maxn],bcc[maxn];
 15 struct edge
 16 {
 17     int u,v,w;
 18 };
 19 stack<edge> st;
 20 
 21 int dfs(int u,int fa)
 22 {
 23    int lowu= pre[u]=++dfsclock;
 24    int child=0;
 25     for(int i=0;i<g[u].size();i++)
 26     {
 27         int v=g[u][i];
 28         edge e;
 29         e.u=u,e.v=v;
 30         if(!pre[v])
 31         {
 32             st.push(e);
 33             child++;
 34             int lowv=dfs(v,u);
 35             lowu=min(lowu,lowv);
 36             if(lowv>=pre[u])
 37             {
 38                 iscut[u]=1;
 39                 bcc_cnt++;
 40                 bcc[bcc_cnt].clear();
 41                 for(;;)
 42                 {
 43                     edge x=st.top();st.pop();
 44                     if(bccno[x.u]!=bcc_cnt)
 45                     {
 46                         bcc[bcc_cnt].push_back(x.u);
 47                         bccno[x.u]=bcc_cnt;
 48                     }
 49                     if(bccno[x.v]!=bcc_cnt)
 50                     {
 51                         bcc[bcc_cnt].push_back(x.v);
 52                         bccno[x.v]=bcc_cnt;
 53                     }
 54                     if(x.u==u&&x.v==v)break;
 55                 }
 56             }
 57         }
 58         else if(pre[v]<pre[u]&&v!=fa)
 59         {
 60             st.push(e);
 61             lowu=min(lowu,pre[v]);
 62         }
 63     }
 64     if(fa<0&&child==1)iscut[u]=0;
 65     return lowu;
 66 }
 67 void find_bcc(int n)
 68 {
 69     int i;
 70     memset(pre,0,sizeof(pre));
 71     cl(iscut,0);
 72     cl(bccno,0);
 73     dfsclock = bcc_cnt = 0;
 74     loop(0,i,n)
 75     if(!pre[i]) dfs(i,-1);
 76    // puts("yes");
 77    // printf("%d  """"""
",bcc_cnt);
 78 }
 79 int odd[maxn],color[maxn];
 80 bool bipartite(int u,int b)
 81 {
 82     int i;
 83     loop(0,i,g[u].size())
 84     {
 85         int v = g[u][i];
 86         if(bccno[v] != b)
 87         continue;
 88         if(color[v] == color[u])
 89         return false;
 90         if(!color[v])
 91         {
 92             color[v] = 3-color[u];
 93             if(!bipartite(v,b))
 94             return false;
 95         }
 96     }
 97     return true;
 98 }
 99 int map[maxn][maxn];
100 int main()
101 {
102     int i,kase = 0,n,m;
103     
104     while(scanf("%d %d",&n,&m))
105     {
106         if(!n)
107         break;
108         memset(map,0,sizeof(map));
109 
110         loop(0,i,n) g[i].clear();
111 
112         loop(0,i,m)
113         {
114             int u,v;
115             scanf("%d %d",&u,&v);
116             u--,v--;
117             map[u][v] = map[v][u] =1;
118         }
119         int j;
120         loop(0,i,n)
121         {
122             loop(i+1,j,n)
123             {
124                 if(!map[i][j])
125                 g[i].push_back(j),g[j].push_back(i);
126             }
127         }
128 
129 
130 
131         find_bcc(n);
132 
133        // cout<<bcc_cnt<<endl;
134 
135         memset(odd,0,sizeof(odd)) ;
136         for(int i=1;i<=bcc_cnt;i++)
137         {
138         memset(color,0,sizeof(color));
139         for(int j=0;j<bcc[i].size();j++)
140             bccno[bcc[i][j]]=i;
141         int u=bcc[i][0];
142         color[u]=1;
143         if(!bipartite(u,i))//判二分图的原因是如果偶数圈会可能是二分图，但是奇数圈不会是~
144             for(int j=0;j<bcc[i].size();j++)
145                 odd[bcc[i][j]]=1;
146         }
147         int ans=n;
148         for(int i=0;i<n;i++)
149             if(odd[i])ans--;
150 
151         printf("%d
",ans);
152     }
153     return 0;
154 }
View Code