#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#define maxn 1001
#define maxm 1000001
using namespace std;
vector<int> to[maxn],dcc[maxn];
bool g[maxn][maxn],able[maxn];//able表示能够参加会议
int dfn[maxn],low[maxn],tot;
int stack[maxn],top;
int col[maxn],cnt;
int vis[maxn];
int n,m,ans;
inline int read(){
register int x(0),f(1); register char c(getchar());
while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }
while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
inline void init(){
for(register int i=1;i<=n;i++) for(register int j=1;j<=n;j++) g[i][j]=false;
for(register int i=1;i<=n;i++) dfn[i]=low[i]=vis[i]=col[i]=able[i]=0;
for(register int i=1;i<=n;i++) to[i].clear(),dcc[i].clear();
tot=cnt=0,ans=0;
}
void tarjan(int u){
dfn[u]=low[u]=++tot;
stack[++top]=u;
for(register int i=0;i<to[u].size();i++){
int v=to[u][i];
if(!dfn[v]){
tarjan(v),low[u]=min(low[u],low[v]);
if(dfn[u]<=low[v]){
int w; cnt++;
do{ w=stack[top--],dcc[cnt].push_back(w); }while(w!=v);
dcc[cnt].push_back(u);
}
}else low[u]=min(low[u],dfn[v]);
}
}
bool check(int u,int c,const int &id){
vis[u]=c;
for(register int i=0;i<to[u].size();i++){
int v=to[u][i];
if(col[v]!=id) continue;
if(!vis[v]){
if(check(v,3-c,id)) return true;
}else if(vis[v]==c) return true;
}
return false;
}
int main(){
while(scanf("%d %d",&n,&m)==2&&n&&m){
init();
for(register int i=1;i<=m;i++){
int u=read(),v=read();
g[u][v]=g[v][u]=true;
}
for(register int i=1;i<=n;i++){
for(register int j=1;j<i;j++) if(!g[i][j]){
to[i].push_back(j),to[j].push_back(i);
}
}
for(register int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
for(register int i=1;i<=cnt;i++){
for(register int j=0;j<dcc[i].size();j++){
col[dcc[i][j]]=i,vis[dcc[i][j]]=0;
}
if(check(dcc[i][0],1,i)){
for(register int j=0;j<dcc[i].size();j++) able[dcc[i][j]]=true;
}
}
for(register int i=1;i<=n;i++) if(!able[i]) ans++;
printf("%d\n",ans);
}
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章