RT，样例都过不了......

思路是缩点求点双，然后二分图判奇环

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#define MAXN 1005
#define MAXM 1000005
using namespace std;
int n,nn,m,dfsTime,dccCount,now,cnt;
int head[MAXM],pre[MAXN],low[MAXN];
int com[MAXN][MAXN],color[MAXN],vis[MAXN];
int knight[MAXN];
bool flag;
struct Edge{
    int next,to;
}edge[MAXM];
stack<int> s;
vector<int> dcc[MAXN];
inline void addEdge(int from,int to){
    edge[++nn].to=to;
    edge[nn].next=head[from];
    head[from]=nn;
}
inline void init(){
    nn=dfsTime=cnt=dccCount=0;
    memset(head,0,sizeof(head));
    memset(pre,0,sizeof(pre));
    memset(low,0,sizeof(low));
    memset(edge,0,sizeof(edge));
    memset(com,0,sizeof(com));
    memset(color,0,sizeof(color));
    memset(vis,0,sizeof(vis));
    memset(knight,0,sizeof(knight));
    while(!s.empty())
        s.pop();
}
void tarjan(int u,int father){
    pre[u]=low[u]=++dfsTime;
    s.push(u);
    if(u==father&&head[u]==0){
        dcc[++dccCount].push_back(u);
        return;
    }
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(pre[v]==0){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=pre[u]){
                dccCount++;
                while(1){
                    int t=s.top();s.pop();
                    dcc[dccCount].push_back(t);
                    if(v==t)
                        break;
                }
                dcc[dccCount].push_back(u);
            }
        }else
            low[u]=min(low[u],pre[v]);
    }
}
void dfs(int u,int colorCount){
    color[u]=colorCount;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(vis[v]!=now)
            continue;
        if(color[v]!=0&&color[v]==colorCount){
            flag=1;
            return;
        }
        if(color[v]==0)
            dfs(v,3-colorCount);
    }
}
int main(){
    while(1){
        scanf("%d%d",&n,&m);
        if(n==0&&m==0)
            break;
        for(int i=1;i<=m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            com[u][v]=com[v][u]=1;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(i!=j&&com[i][j]==0)
                    addEdge(i,j);
            }
        for(int i=1;i<=n;i++)
            if(pre[i]==0)
                tarjan(i,0);
        for(int i=1;i<=dccCount;i++){
            now=i;
            for(int j=0;j<dcc[i].size();j++){
                vis[dcc[i][j]]=now;
                color[dcc[i][j]]=0;
            }
            flag=0;
            dfs(dcc[i][0],1);
            if(flag)
                for(int j=0;j<dcc[i].size();j++)
                    knight[j]=1;
        }
        for(int i=1;i<=n;i++)
            if(knight[i]==0)
                cnt++;
        printf("%d\n",cnt);
    }
    return 0;
}