本文主要是介绍poj-2942-点双联通，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
亚瑟王要在圆桌上召开骑士会议，为了不引发骑士之间的冲突，并且能够让会议的议题有令人满意的结果，每次开会前都必须对出席会议的骑士有如下要求：
1、 相互憎恨的两个骑士不能坐在直接相邻的2个位置；
2、 出席会议的骑士数必须是奇数，这是为了让投票表决议题时都能有结果。
如果出现有某些骑士无法出席所有会议（例如这个骑士憎恨所有的其他骑士），则亚瑟王为了世界和平会强制把他剔除出骑士团。
现在给定准备去开会的骑士数n，再给出m对憎恨对（表示某2个骑士之间使互相憎恨的），问亚瑟王至少要剔除多少个骑士才能顺利召开会议？
注意：1、所给出的憎恨关系一定是双向的，不存在单向憎恨关系。
2、由于是圆桌会议，则每个出席的骑士身边必定刚好有2个骑士。即每个骑士的座位两边都必定各有一个骑士。
3、一个骑士无法开会，就是说至少有3个骑士才可能开会。
做法：
1，先对憎恶关系建图
2，建立上图的反图，这时候，图表明的关系是可以坐在一起。
3，求图中所有点大于等于3的圈。（tarjan求点双连通）
4，求3的求出的圈是不是奇圈。（交叉染色法）
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define maxn 1001
#define maxm 1000005
vector<int>vc[maxn];
stack<int>st;
vector<int>vec;
int maps[maxn][maxn];
int n,m;
struct list
{int u;int e;int next;
}edge[maxm*2];
int tops,head[maxm*2],vis[maxm*2];
int nums,dnf[maxn],low[maxn],instack[maxn],times;
int mark[maxn],odd[maxn],visit[maxn];;
void add(int x,int y)
{// printf("%d---%d %d\n",tops,x,y);edge[tops].u=x;edge[tops].e=y;edge[tops].next=head[x];head[x]=tops++;
}
void init()
{int a,b,i,j;for(i=0;i<=n;i++)for(j=0;j<=n;j++)maps[i][j]=0;for(i=0;i<m;i++){scanf("%d%d",&a,&b);maps[a][b]=maps[b][a]=-1;}
}
void fantu()
{int i,j;tops=0;for(i=0;i<=m*2;i++)head[i]=-1;for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)if(maps[i][j]==0){add(i,j);add(j,i);}
}
int find(int x)
{int i;for(i=head[x];i!=-1;i=edge[i].next){int y=edge[i].e;// cout<<x<<" -- "<<y<<endl;if(mark[y]){if(visit[y]==-1){visit[y]=(visit[x]+1)%2;if(find(y))return 1;}else if(visit[x]==visit[y])return 1;}}return 0;
}
void dos(int x)
{int i;memset(visit,-1,sizeof(visit));visit[x]=0;if(find(x)){for(i=0;i<=n;i++)if(mark[i])odd[i]=1;}
}
void tarjan(int x)
{int i;low[x]=dnf[x]=times++;for(i=head[x];i!=-1;i=edge[i].next){if(vis[i])continue;vis[i]=vis[i^1]=1;int y=edge[i].e;// printf("%d-%d----\n",x,y);if(!dnf[y]){st.push(i);tarjan(y);low[x]=min(low[x],low[y]);if(low[y]>=dnf[x]){memset(mark,0,sizeof(mark));int yw=0;int cc=0;while(1){cc++;yw=st.top();st.pop();//printf("%d ",yw);mark[edge[yw].e]=mark[edge[yw].u]=1;if(edge[yw].u==x)break;}// cout<<endl;if(cc>=3)dos(x);}}else if(dnf[y]<dnf[x]){st.push(i);low[x]=min(low[x],dnf[y]);}}
}
void chushihua()
{int i;for(i=0;i<=n;i++)low[i]=dnf[i]=instack[i]=0;for(i=0;i<=n;i++)mark[i]=odd[i]=0;nums=0;times=1;memset(vis,0,sizeof(vis));while(!st.empty())st.pop();vec.clear();
}
int sums()
{int i,s=0;for(i=1;i<=n;i++)if(odd[i])s++;// cout<<" s="<<s<<endl;return s;
}
int main()
{//freopen("data.in","r",stdin);int i;while(scanf("%d%d",&n,&m)&&(n||m)){init();fantu();chushihua();for(i=1;i<=n;i++)if(!dnf[i])tarjan(i);printf("%d\n",n-sums());}return 0;
}这篇关于poj-2942-点双联通的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
