UVAlive3523 Knights of the Round Table（bcc）

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18122
【思路】
点-双连通分量
求出bcc，判断每个bcc是否为二分图，如果不是二分图则bcc中一定存在一个奇圈，则bcc中的任意一点一定位于一个奇圈上。
【代码】
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<stack>
  4 #include<vector>
  5 using namespace std;
  6 
  7 typedef long long LL;
  8 const int maxn = 2000+10;
  9 
 10 struct Edge{ int u,v;
 11 };
 12 
 13 int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cnt;
 14 vector<int> G[maxn],bcc[maxn];
 15 
 16 stack<Edge> S;
 17 
 18 int dfs(int u,int fa) {
 19     int lowu=pre[u]=++dfs_clock;
 20     int ch=0;
 21     for(int i=0;i<G[u].size();i++) {
 22         int v=G[u][i];
 23         Edge e=(Edge) {u,v};
 24         if(!pre[v]) {
 25             S.push(e);
 26             ch++;
 27             int lowv=dfs(v,u);
 28             lowu=min(lowu,lowv);
 29             if(lowv>=pre[u]) {
 30                 iscut[u]=1;
 31                 bcc_cnt++; bcc[bcc_cnt].clear();
 32                 for(;;) {
 33                     Edge x=S.top(); S.pop();
 34                     if(bccno[x.u]!=bcc_cnt) bcc[bcc_cnt].push_back(x.u),bccno[x.u]=bcc_cnt;
 35                     if(bccno[x.v]!=bcc_cnt) bcc[bcc_cnt].push_back(x.v),bccno[x.v]=bcc_cnt;
 36                     if(x.u==u && x.v==v) break;
 37                 }
 38             }
 39         }
 40         else if(pre[v]<pre[u] && v!=fa) {
 41             S.push(e);  lowu=min(lowu,pre[v]); 
 42         }
 43     }
 44     if(fa<0 && ch==1) iscut[u]=0;
 45     return lowu; 
 46 }
 47 void find_bcc(int n) {
 48     memset(pre,0,sizeof(pre));
 49     memset(iscut,0,sizeof(iscut));
 50     memset(bccno,0,sizeof(bccno));
 51     dfs_clock=bcc_cnt=0;
 52     for(int i=0;i<n;i++)
 53         if(!pre[i]) dfs(i,-1);
 54 }
 55 
 56 int color[maxn],odd[maxn];
 57 bool judge(int u,int b) {
 58     for(int i=0;i<G[u].size();i++) {
 59         int v=G[u][i];  if(bccno[v]!=b) continue;
 60         if(color[v]==color[u]) return false;
 61         if(!color[v]) {
 62             color[v]=3-color[u];
 63             if(!judge(v,b)) return false;
 64         }
 65     }
 66     return true;
 67 }
 68 
 69 int n,m;
 70 int A[maxn][maxn];
 71 
 72 void init() {
 73     memset(A,0,sizeof(A));
 74     for(int i=0;i<n;i++) G[i].clear();
 75 }
 76 
 77 int main() {
 78     while(scanf("%d%d",&n,&m)==2 && n ) {
 79         init();
 80         int u,v;
 81         for(int i=0;i<m;i++) {
 82             scanf("%d%d",&u,&v);
 83             u--,v--;
 84             A[u][v]=A[v][u]=1;
 85         }
 86         for(int i=0;i<n;i++) for(int j=i+1;j<n;j++)
 87             if(!A[i][j]) G[i].push_back(j),G[j].push_back(i);
 88         find_bcc(n);
 89         memset(odd,0,sizeof(odd));
 90         for(int i=1;i<=bcc_cnt;i++) {
 91             memset(color,0,sizeof(color));
 92             for(int j=0;j<bcc[i].size();j++) bccno[bcc[i][j]]=i;
 93             int u=bcc[i][0];
 94             color[u]=1; 
 95             if(!judge(u,i)) 
 96                 for(int j=0;j<bcc[i].size();j++) odd[bcc[i][j]]=1;
 97         }
 98         int ans=n;
 99         for(int i=0;i<n;i++) if(odd[i]) ans--;
100         printf("%d
",ans);
101     }
102     return 0;
103 }