【题意】
给你n个人和m组关系，每组关系表示两个人相互憎恨，而且相互憎恨的人不能在参加一场会议相邻着坐，而且每次会议参加的人数必须为奇数，问最多有多少人不能同时参加一场会议。
【分析】
为什么我没有做圆桌骑士？为什么我没有做圆桌骑士？为什么我没有做圆桌骑士？
记得以前明明做过嘛- -啊- -怎么找不到带代码，晕..
再做一次啊。
其实如果不是一道经典题，还是很难的（像是我这样子的水平，可能建图都想不到ORZ）
可以把不相互憎恨的两个人之间连一条边，那么每一次参加会议的人就必须在同一个双连通分量上，这样才能形成过一个环形图，关键是如何判断这个环是不是一个奇环，根据二分图的定义，我们知道如果一个环是二分图，那么这个环必定是偶环。
还有一个定理：若某个点双连通分量中存在奇环，则该点双联通分量中所有点都在某个奇环内。（这个东东画个图想想就好了，想想点双连通的性质，奇数=偶数+奇数）
判奇环用厉害的染色法。。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
#define Maxn 1010 bool a[Maxn][Maxn]; struct node
{
int x,y,next;
}t[Maxn];int len;
int first[Maxn]; int mymin(int x,int y) {return x<y?x:y;} void ins(int x,int y)
{
t[++len].x=x;t[len].y=y;
t[len].next=first[x];first[x]=len;
} int dfn[Maxn],low[Maxn]; stack<int > s;
vector<int > v[Maxn];
int vl,cnt;
int col[Maxn];
bool q[Maxn]; void ffind(int x,int f)
{
dfn[x]=low[x]=++cnt;
s.push(x);
for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)
{
int y=t[i].y;
if(!dfn[y])
{
ffind(y,x);
low[x]=mymin(low[x],low[y]);
if(low[y]>=dfn[x])
{
vl++;
// memset(v[vl],0,sizeof(v[vl]));
v[vl].clear();
while()
{
int z=s.top();
v[vl].push_back(z);
if(z==x) break;
s.pop();
}
}
}
else low[x]=mymin(low[x],dfn[y]);
}
} bool dfs(int x)
{
for(int i=first[x];i;i=t[i].next) if(col[t[i].y]!=-)
{
int y=t[i].y;
if(col[y]!=-&&col[y]==col[x]) return ;
else if(col[y]==-)
{
col[y]=-col[x];
if(!dfs(y)) return ;
}
}
return ;
} int main()
{
int n,m;
while()
{
scanf("%d%d",&n,&m);
if(n==&&m==) break;
memset(a,,sizeof(a));
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
a[x][y]=a[y][x]=;
}
len=;vl=;cnt=;
memset(first,,sizeof(first));
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++) if(a[i][j])
{
ins(i,j);ins(j,i);
}
memset(dfn,,sizeof(dfn));
while(!s.empty()) s.pop();
for(int i=;i<=n;i++) if(!dfn[i])
{
ffind(i,);
}
for(int i=;i<=n;i++) col[i]=-;
memset(q,,sizeof(q));
for(int i=;i<=vl;i++)
{
for(int j=;j<v[i].size();j++) col[v[i][j]]=-;
col[v[i][]]=;
int x=v[i][];
if(!dfs(x))
{
for(int j=;j<v[i].size();j++) q[v[i][j]]=;
}
for(int j=;j<v[i].size();j++) col[v[i][j]]=-;
}
int ans=;
for(int i=;i<=n;i++) if(q[i]) ans++;
printf("%d\n",ans);
}
return ;
}
[LA 3523]
2016-10-20 21:38:24