搜索双连通分量。深度优先搜索过程中，用一个栈保存所有经过的节点，判断割点，碰到割点就标记当前栈顶的结点并退栈，直到当前结点停止并标记当前割点。标记过的结点处于同一个双连通分量。
交叉染色搜索奇圈。在一个节点大于2的双连通分量中，必定存在一个圈经过该连通分量的所有结点；如果这个圈是奇圈，则该连通分量内的所有的点都满足条件；若这个圈是偶圈，如果包含奇圈，则必定还有一个奇圈经过所有剩下的点。因此一个双连通分量中只要存在一个奇圈，那么该双联通分量内的所有的点都处于一个奇圈中，在题目中，即武士可以坐成一圈。根据这个性质，只需要在一个双联通分量内找奇圈即可判断该双联通分量是否满足条件。交叉染色法就是在dfs的过程中反复交换着用两种不同的颜色对点染色，若某次dfs中当前结点的子节点和当前结点同色，则找到奇圈。
View Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<vector> 7 #include<stack> 8 using namespace std; 9 #define N 1010 10 vector<int> g[N]; 11 stack<int> sta; 12 int color[N],num[N],dfn[N],low[N],belg[N*10],in[N],vis[N],net[N][N]; 13 int idx,type; 14 bool dfs(int u,int val){ 15 color[u]=val; 16 for(int i=0;i<g[u].size();i++){ 17 int v=g[u][i]; 18 if(belg[v]!=belg[u])continue; 19 if(color[v]==-1){ 20 if(dfs(v,1-val))return true; 21 } 22 else if(color[v]==val)return true; 23 } 24 return false; 25 } 26 void targan(int u,int fa){ 27 dfn[u]=low[u]=idx++; 28 in[u]=1; 29 sta.push(u); 30 for(int i=0;i<g[u].size();i++){ 31 32 int v=g[u][i]; 33 if(v==fa)continue; 34 if(!dfn[v]){ 35 targan(v,u); 36 low[u]=min(low[u],low[v]); 37 if(dfn[u]<=low[v]){ 38 int c=0; 39 while(1){ 40 int t=sta.top();sta.pop(); 41 belg[t]=type; 42 in[t]=0; 43 num[c++]=t; 44 if(t==v)break; 45 } 46 47 belg[u]=type; 48 num[c++]=u; 49 type++; 50 memset(color,-1,sizeof(color)); 51 if(c>=3&&dfs(u,1)){ 52 for(int i=0;i<c;i++){ 53 vis[num[i]]=1; 54 } 55 } 56 } 57 } 58 else if(in[v])low[u]=min(low[u],dfn[v]); 59 } 60 } 61 int main(){ 62 int n,m; 63 while(scanf("%d%d",&n,&m),n||m){ 64 idx=type=1; 65 memset(net,0,sizeof(net)); 66 memset(dfn,0,sizeof(dfn)); 67 memset(in,0,sizeof(in)); 68 memset(belg,0,sizeof(belg)); 69 memset(vis,0,sizeof(vis)); 70 memset(g,0,sizeof(g)); 71 while(!sta.empty())sta.pop(); 72 for(int i=1;i<=m;i++){ 73 int a,b; 74 scanf("%d%d",&a,&b); 75 net[a][b]=net[b][a]=1; 76 } 77 for(int i=1;i<=n;i++){ 78 for(int j=1;j<=n;j++){ 79 if(!net[i][j]&&i!=j){ 80 g[i].push_back(j); 81 //cout<<i<<" "<<j<<endl; 82 } 83 } 84 } 85 for(int i=1;i<=n;i++){ 86 if(!dfn[i])targan(i,0); 87 } 88 int sum=0; 89 for(int i=1;i<=n;i++){ 90 sum+=vis[i]; 91 } 92 printf("%d\n",n-sum); 93 } 94 return 0; 95 }