题意:有\(n\)个骑士经常举行圆桌会议，商讨大事.每次圆桌会议至少有\(3\)个骑士参加，且相互憎恨的骑士不能坐在圆桌的相邻位置.如果发生意见分歧，则需要举手表决，因此参加会议的骑士数目必须是大于1的奇数，以防止赞同和反对票一样多.知道那些骑士相互憎恨之后，你的任务是统计有多少骑士不可能参加任何一个会议.\(n<=1000,m<=10^6\).
分析:建原图的"补图":如果两名骑士没有憎恨关系,则在两个节点之间建立一条无向边.跑无向图\(Tarjan\)求出图中所有的\(v-DCC\),用二分图染色法判定每个\(v-DCC\)中是否存在奇环即可.若存在奇环,则该\(v-DCC\)中的所有骑士都可以参加会议(因为它们必定都在某个奇环中).
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=1005;
const int M=1000005;
int n,m,ans,w[N][N];
int tot,head[N],nxt[M],to[M];
int tim,top,cnt,root,BJ;
int dfn[N],low[N],st[M],cut[N];
int belong[N],visit[N],bj[N];
vector<int>dcc[N];
inline void add(int a,int b){nxt[++tot]=head[a];head[a]=tot;to[tot]=b;}
inline void tarjan(int x){
dfn[x]=low[x]=++tim;st[++top]=x;
if(x==root&&!head[x]){
dcc[++cnt].push_back(x);
return;
}
int flag=0;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
++flag;
if(x!=root||flag>1)cut[x]=1;
++cnt;int z;
do{
z=st[top--];
dcc[cnt].push_back(z);
}while(z!=y);
dcc[cnt].push_back(x);
}
}
else low[x]=min(low[x],dfn[y]);
}
}
inline void dfs(int x,int color){
visit[x]=color;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(belong[y]!=belong[x])continue;
if(!visit[y])dfs(y,3-color);
else if(visit[y]==color){
BJ=1;return;
}
}
}
int main(){
while(1){
n=read();m=read();if(!n&&!m)break;
tot=0;ans=0;tim=0;top=0;cnt=0;
for(int i=1;i<=n;++i){
head[i]=belong[i]=0;
dfn[i]=low[i]=0;
cut[i]=bj[i]=st[i]=0;
}//多组数据初始化,不想用memset...
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)w[i][j]=0;//初始化
for(int i=1;i<=n;++i)dcc[i].clear();//清空
for(int i=1;i<=m;++i){
int a=read(),b=read();
w[a][b]=w[b][a]=1;//标记憎恨关系
}
for(int i=1;i<n;++i)
for(int j=i+1;j<=n;++j)
if(!w[i][j])add(i,j),add(j,i);//建立补图
for(int i=1;i<=n;++i)if(!dfn[i])root=i,tarjan(i);//tarjan求v-dcc
for(int i=1;i<=cnt;++i){
for(int j=0;j<dcc[i].size();++j)
belong[dcc[i][j]]=i,visit[dcc[i][j]]=0;//初始化
BJ=0;dfs(dcc[i][0],1);//二分图染色法判定是否存在奇环
if(BJ){//如果存在,标记这个v-dcc内的点不用被踢出去
for(int j=0;j<dcc[i].size();++j)bj[dcc[i][j]]=1;
}
}
for(int i=1;i<=n;++i)if(!bj[i])++ans;
printf("%d\n",ans);
}
return 0;
}