链接：https://vjudge.net/problem/POJ-2942
题意：给定一个无向图，求出补图，然后求补图中有多少个点不属于任何奇圈。
分析：首先是骑士有不能坐在一起的人，不好想，反过来想，相当于和其他人可以坐在一起，连一条边，围成一圈就变成了该点是否在某个点双连通分量里，所以先用Tarjan算法处理出所有的点双连通分量。然后还有一个要求，该点得在某个含奇数个点的点双连通分量里。
首先点双连通分量有两个性质：1.如果该分量里有一个奇圈，那么其他所有点也必然在某个奇圈中；2.含有一个奇圈的充要条件是该分量不是二分图。
- - 知道了这些性质就好做点了。。处理完点双连通分量以后，对每个分量都用染色法判断是否是二分图，如果是二分图，那么这些人不能坐在一起开会，否则每个点都标记一下，等处理完所有分量后统计下没被标记的点数，就是答案。注意当分量中只有两个点时，虽然是二分图，但是也不满足条件。
是道好题。。但wa了9发才过。。主要是Tarjan的模板出错了没找到。。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<stack> 5 #include<vector> 6 #include<set> 7 using namespace std; 8 const int maxn=1005; 9 int dfn[maxn],low[maxn],fa[maxn],cnt=0,bcc_cnt=0; 10 int n,m; 11 bool vis[maxn],Is_cut[maxn]; 12 struct Edge{ 13 int u,v; 14 Edge(int _u,int _v):u(_u),v(_v){} 15 }; 16 vector<Edge> edges; 17 vector<int>G[maxn]; 18 set<int>bcc[maxn]; 19 int g[maxn][maxn]; 20 stack<int>sta; 21 void AddEdge(int u,int v){ 22 edges.push_back(Edge(u,v)); 23 edges.push_back(Edge(v,u)); 24 G[u].push_back(edges.size()-2); 25 G[v].push_back(edges.size()-1); 26 } 27 void dfs(int u){ 28 if(vis[u])return ; 29 vis[u]=true; 30 dfn[u]=cnt++; 31 low[u]=dfn[u]; 32 int child=0; 33 for(int i=0;i<G[u].size();i++){ 34 int v=edges[G[u][i]].v; 35 if(!vis[v]){ 36 sta.push(G[u][i]); 37 fa[v]=u; 38 child++; 39 dfs(v); 40 low[u]=min(low[u],low[v]); 41 if(low[v]>=dfn[u]){ 42 Is_cut[u]=true; 43 bcc[bcc_cnt].clear(); 44 while(1){ 45 Edge e=edges[sta.top()];sta.pop(); 46 bcc[bcc_cnt].insert(e.u); 47 bcc[bcc_cnt].insert(e.v); 48 if(e.u==u&&e.v==v)break; 49 } 50 bcc_cnt++; 51 } 52 }else if(dfn[v]<dfn[u]&&v!=fa[u]){ 53 sta.push(G[u][i]); 54 low[u]=min(low[u],dfn[v]); 55 } 56 } 57 if(fa[u]==-1&&child<=1)Is_cut[u]=false; 58 } 59 void Tarjan(){ 60 memset(vis,0,sizeof(vis)); 61 memset(Is_cut,0,sizeof(Is_cut)); 62 for(int i=1;i<=n;i++){ 63 if(!vis[i]){ 64 fa[i]=-1; 65 dfs(i); 66 } 67 } 68 } 69 70 bool ok[maxn]; 71 int color[maxn]; 72 void init(){ 73 edges.clear(); 74 for(int i=1;i<=n;i++)G[i].clear(); 75 cnt=bcc_cnt=0; 76 while(!sta.empty())sta.pop(); 77 memset(ok,0,sizeof(ok)); 78 for(int i=1;i<=n;i++){ 79 for(int j=1;j<=n;j++)g[i][j]=1; 80 g[i][i]=0; 81 } 82 } 83 bool Is_btg(set<int> &S){ 84 memset(color,0,sizeof(color)); 85 stack<int> s; 86 s.push(*S.begin()); 87 color[*S.begin()]=1; 88 while(!s.empty()){ 89 int u=s.top();s.pop(); 90 for(int i=0;i<G[u].size();i++){ 91 int v=edges[G[u][i]].v; 92 if(!S.count(v))continue; 93 if(color[v]==color[u])return false; 94 if(!color[v]){ 95 s.push(v); 96 color[v]=-color[u]; 97 } 98 } 99 } 100 return true; 101 } 102 int main(){ 103 // freopen("e:\in.txt","r",stdin); 104 while(scanf("%d%d",&n,&m)!=EOF&&(n+m)){ 105 init(); 106 int u,v; 107 for(int i=0;i<m;i++){ 108 scanf("%d%d",&u,&v); 109 g[u][v]=0;g[v][u]=0; 110 } 111 for(int i=1;i<=n;i++){ 112 for(int j=i+1;j<=n;j++) 113 if(g[i][j])AddEdge(i,j); 114 } 115 // for(int i=1;i<=n;i++){ 116 // for(int j=0;j<G[i].size();j++){ 117 // cout<<G[i][j]<<' '; 118 // } 119 // cout<<endl; 120 // } 121 Tarjan(); 122 // for(int i=0;i<bcc_cnt;i++){ 123 // for(set<int>::iterator it=bcc[i].begin();it!=bcc[i].end();it++){ 124 // cout<<*it<<' '; 125 // } 126 // cout<<endl; 127 // } 128 for(int i=0;i<bcc_cnt;i++){ 129 int len=bcc[i].size(); 130 if(len>2&&!Is_btg(bcc[i])){ 131 for(set<int>::iterator it=bcc[i].begin();it!=bcc[i].end();it++) 132 ok[*it]=true; 133 } 134 } 135 int ans=0; 136 for(int i=1;i<=n;i++) 137 if(!ok[i])ans++; 138 printf("%d ",ans); 139 140 } 141 return 0; 142 }