UVAlive3523 Knights of the Round Table（bcc）

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18122

【思路】

点-双连通分量

求出bcc，判断每个bcc是否为二分图，如果不是二分图则bcc中一定存在一个奇圈，则bcc中的任意一点一定位于一个奇圈上。

【代码】

 #include<cstdio>

 #include<cstring>

 #include<stack>

 #include<vector>

 using namespace std;

 typedef long long LL;

 const int maxn = +;

 struct Edge{ int u,v;

 };

 int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cnt;

 vector<int> G[maxn],bcc[maxn];

 stack<Edge> S;

 int dfs(int u,int fa) {

     int lowu=pre[u]=++dfs_clock;

     int ch=;

     for(int i=;i<G[u].size();i++) {

         int v=G[u][i];

         Edge e=(Edge) {u,v};

         if(!pre[v]) {

             S.push(e);

             ch++;

             int lowv=dfs(v,u);

             lowu=min(lowu,lowv);

             if(lowv>=pre[u]) {

                 iscut[u]=;

                 bcc_cnt++; bcc[bcc_cnt].clear();

                 for(;;) {

                     Edge x=S.top(); S.pop();

                     if(bccno[x.u]!=bcc_cnt) bcc[bcc_cnt].push_back(x.u),bccno[x.u]=bcc_cnt;

                     if(bccno[x.v]!=bcc_cnt) bcc[bcc_cnt].push_back(x.v),bccno[x.v]=bcc_cnt;

                     if(x.u==u && x.v==v) break;

                 }

             }

         }

         else if(pre[v]<pre[u] && v!=fa) {

             S.push(e);  lowu=min(lowu,pre[v]);

         }

     }

     if(fa< && ch==) iscut[u]=;

     return lowu;

 }

 void find_bcc(int n) {

     memset(pre,,sizeof(pre));

     memset(iscut,,sizeof(iscut));

     memset(bccno,,sizeof(bccno));

     dfs_clock=bcc_cnt=;

     for(int i=;i<n;i++)

         if(!pre[i]) dfs(i,-);

 }

 int color[maxn],odd[maxn];

 bool judge(int u,int b) {

     for(int i=;i<G[u].size();i++) {

         int v=G[u][i];  if(bccno[v]!=b) continue;

         if(color[v]==color[u]) return false;

         if(!color[v]) {

             color[v]=-color[u];

             if(!judge(v,b)) return false;

         }

     }

     return true;

 }

 int n,m;

 int A[maxn][maxn];

 void init() {

     memset(A,,sizeof(A));

     for(int i=;i<n;i++) G[i].clear();

 }

 int main() {

     while(scanf("%d%d",&n,&m)== && n ) {

         init();

         int u,v;

         for(int i=;i<m;i++) {

             scanf("%d%d",&u,&v);

             u--,v--;

             A[u][v]=A[v][u]=;

         }

         for(int i=;i<n;i++) for(int j=i+;j<n;j++)

             if(!A[i][j]) G[i].push_back(j),G[j].push_back(i);

         find_bcc(n);

         memset(odd,,sizeof(odd));

         for(int i=;i<=bcc_cnt;i++) {

             memset(color,,sizeof(color));

             for(int j=;j<bcc[i].size();j++) bccno[bcc[i][j]]=i;

             int u=bcc[i][];

             color[u]=;

             if(!judge(u,i))

                 for(int j=;j<bcc[i].size();j++) odd[bcc[i][j]]=;

         }

         int ans=n;

         for(int i=;i<n;i++) if(odd[i]) ans--;

         printf("%d\n",ans);

     }

     return ;

 }