简述：
- 缩点+二分图染色（判奇环）
易错点：
- 为了防止错误加边（自环，即i==j），可将加边时的第二层遍历从i+1开始，由对称性可知加边无错误.
- vector直接用[]比at()更美观.
- 对于每个dcc都要重置一次color，这是因为同一个点可能属于多个dcc.
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN=2e3,MAXM=2e6;
struct Edge{
int from,to,w,nxt;
}e[MAXM];
int head[MAXN],edgeCnt=1;
void addEdge(int u,int v,int w){
e[++edgeCnt].from=u;
e[edgeCnt].to=v;
e[edgeCnt].w=w;
e[edgeCnt].nxt=head[u];
head[u]=edgeCnt;
}
int dfn[MAXN],dfnCnt=0,low[MAXN];
vector<int> dcc[MAXN];
int dccCnt=0,c[MAXN];//in which dcc
int stck[MAXN],top=0;
void tarjan(int x,int root){
dfn[x]=low[x]=++dfnCnt;
stck[++top]=x;
if(x==root&&(!head[x])){
dcc[++dccCnt].push_back(x);
return;
}
for(int i=head[x];i;i=e[i].nxt){
int nowV=e[i].to;
if(!dfn[nowV]){
tarjan(nowV,root);
low[x]=min(low[x],low[nowV]);
if(low[nowV]>=dfn[x]){
int y;dccCnt++;
do{
y=stck[top--];
dcc[dccCnt].push_back(y);
}while(y!=nowV);
dcc[dccCnt].push_back(x);
}
}else low[x]=min(low[x],dfn[nowV]);
}
}
bool canAttend[MAXN],flag=0;
int color[MAXN];
void dfs(int x,int restColor){
color[x]=restColor;
for(int i=head[x];i;i=e[i].nxt){
int nowV=e[i].to;
if(c[nowV]!=c[x])continue;
if(!color[nowV])dfs(nowV,3-restColor);
else if(color[nowV]==color[x]){
flag=1;
return;
}
}
}
bool hate[MAXN][MAXN];
int n;
void init(){
memset(head,0,sizeof(head));
edgeCnt=1;
memset(hate,0,sizeof(hate));
memset(dfn,0,sizeof(dfn));
dfnCnt=0;
memset(low,0,sizeof(low));
for(int i=1;i<=n;i++){
dcc[i].clear();
}
dccCnt=0;
memset(c,0,sizeof(c));
memset(canAttend,0,sizeof(canAttend));
top=0;
}
int main(){
while(1){
init();
int m;
scanf("%d%d",&n,&m);
if(!n||!m)break;
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
hate[a][b]=hate[b][a]=1;
}
for(int i=1;i<n;i++){//
for(int j=i+1;j<=n;j++){
if(!hate[i][j]){
addEdge(i,j,1);
addEdge(j,i,1);
}
}
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i,i);
}
for(int i=1;i<=dccCnt;i++){
for(int j=0;j<dcc[i].size();j++){
c[dcc[i][j]]=i;//
color[dcc[i][j]]=0;//
}
flag=0;
dfs(dcc[i][0],1);
if(flag){//can attend
for(int j=0;j<dcc[i].size();j++){
canAttend[dcc[i][j]]=1;
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
if(!canAttend[i])ans++;
}
printf("%d
",ans);
}
return 0;
}