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;
}
补充：软件开发 , C++ ,
