LA 3523 圆桌骑士（二分图染色+点双连通分量）

https://vjudge.net/problem/UVALive-3523

题意：

有n个骑士经常举行圆桌会议，商讨大事。每次圆桌会议至少应有3个骑士参加，且相互憎恨的骑士不能坐在圆桌旁的相邻位置。如果发生意见分歧，则需要举手表决，因此参加会议的骑士数目必须是奇数。

统计有多少个骑士不可能参加任何一个会议。

思路：

把不相互憎恨的骑士之间连一条无向边。

因为是圆桌，所以骑士之间要构成一个环，相当于是一个点双连通分量的模型。

环的点的个数得是奇数，这就需要用到前面二分图染色的知识，如果是偶数，则是二分图。

不能参加任何会议的骑士就是不在任何奇圈中的。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<vector>
  6 #include<stack>
  7 #include<queue>
  8 #include<cmath>
  9 #include<map>
 10 using namespace std;
 11 
 12 const int maxn=1000+5;
 13 
 14 struct Edge
 15 {
 16     int u,v;
 17     Edge(int x,int y):u(x),v(y){}
 18 };
 19 stack<Edge> S;
 20 
 21 int n,m;
 22 int A[maxn][maxn];
 23 int color[maxn];
 24 int odd[maxn];
 25 int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cnt;
 26 vector<int> G[maxn],bcc[maxn];
 27 
 28 //二分图染色
 29 bool bipartite(int u,int b)
 30 {
 31     for(int i=0;i<G[u].size();i++)
 32     {
 33         int v=G[u][i];
 34         if(bccno[v]!=b)  continue;
 35         if(color[v]==color[u])  return false;
 36         if(!color[v])
 37         {
 38             color[v]=3-color[u];
 39             if(!bipartite(v,b))  return false;
 40         }
 41     }
 42     return true;
 43 }
 44 
 45 int dfs(int u,int fa)
 46 {
 47     int lowu=pre[u]=++dfs_clock;
 48     int child=0;
 49     for(int i=0;i<G[u].size();i++)
 50     {
 51         int v=G[u][i];
 52         Edge e=Edge(u,v);
 53         if(!pre[v])
 54         {
 55             S.push(e);
 56             child++;
 57             int lowv=dfs(v,u);
 58             lowu=min(lowu,lowv);
 59             if(lowv>=pre[u])
 60             {
 61                 iscut[u]=true;
 62                 bcc_cnt++; bcc[bcc_cnt].clear();
 63                 for(;;)
 64                 {
 65                     Edge x=S.top(); S.pop();
 66                     if(bccno[x.u]!=bcc_cnt)  {bcc[bcc_cnt].push_back(x.u);bccno[x.u]=bcc_cnt;}
 67                     if(bccno[x.v]!=bcc_cnt)  {bcc[bcc_cnt].push_back(x.v);bccno[x.v]=bcc_cnt;}
 68                     if(x.u==u&&x.v==v)   break;
 69                 }
 70             }
 71         }
 72         else if(pre[v]<pre[u] && v!=fa)
 73         {
 74             S.push(e);
 75             lowu=min(lowu,pre[v]);
 76         }
 77     }
 78     if(fa<0 && child==1)   iscut[u]=0;
 79     return lowu;
 80 }
 81 
 82 void find_bcc(int n)
 83 {
 84     memset(pre,0,sizeof(pre));
 85     memset(iscut,0,sizeof(iscut));
 86     memset(bccno,0,sizeof(bccno));
 87     dfs_clock=bcc_cnt=0;
 88     for(int i=0;i<n;i++)
 89             if(!pre[i])  dfs(1,-1);
 90 }
 91 
 92 int main()
 93 {
 94     //freopen("D:\input.txt","r",stdin);
 95     while(~scanf("%d%d",&n,&m) && n)
 96     {
 97         for(int i=0;i<n;i++)   G[i].clear();
 98         memset(A,0,sizeof(A));
 99         while(m--)
100         {
101             int u,v;
102             scanf("%d%d",&u,&v);
103             u--;
104             v--;
105             A[u][v]=A[v][u]=1;
106         }
107         for(int i=0;i<n;i++)
108         {
109             for(int j=i+1;j<n;j++)
110             {
111                 if(!A[i][j])  {G[i].push_back(j);G[j].push_back(i);}
112             }
113         }
114         find_bcc(n);
115         memset(odd,0,sizeof(odd));
116         for(int i=1;i<=bcc_cnt;i++)
117         {
118             memset(color,0,sizeof(color));
119             for(int j=0;j<bcc[i].size();j++)   bccno[bcc[i][j]]=i;   //给同一个连通分量的点加上同一个编号
120             int u=bcc[i][0];
121             color[u]=1;
122             if(!bipartite(u,i))                                        //如果是奇圈，给连通分量里的点做上标记
123             {
124                 for(int j=0;j<bcc[i].size();j++)   odd[bcc[i][j]]=1;
125             }
126         }
127         int ans=n;
128         for(int i=0;i<n;i++)
129             if(odd[i])  ans--;
130         printf("%d
",ans);
131     }
132     return 0;
133 }