C++语言: 高亮代码由发芽网提供

///头文件等等省略
#define MAX 1010
#define mymin(a,b) (a>b?b:a)

int graph[MAX][MAX];
int head[MAX];
struct node{
    int u,v,next;
}edge[MAX*MAX+100];
int edge_count;
int expelled[MAX];
struct node point_dcc[MAX*MAX+100];
int head2[MAX];
int top;
struct edge_node{
    int u,v;
    edge_node(int uu,int vv){u = uu; v = vv;}
};
deque<edge_node> my_deque;

void add2(int u,int v){
    point_dcc[edge_count].u = u;
    point_dcc[edge_count].v = v;
    point_dcc[edge_count].next = head2[u]; head2[u] = edge_count++;
}
int visited2[MAX];
int isBipartite(int uu,int colo){
    //判断当前的点连通分量是是不是二分图
    //如果是二分图则它含有奇数圈
    //如果它含有奇数圈 则该 点双连通图 的所有点都能找到一个奇数圈使相应的点在某个奇数圈上
    queue<int> my_queue;
    my_queue.push(uu);visited2[uu] = colo;
    while(!my_queue.empty()){
        int u = my_queue.front(); my_queue.pop();

        for(int i = head2[u];i != -1; i = point_dcc[i].next){
            int v = point_dcc[i].v;
            if(visited2[v] != -1){
                if(visited2[u] == visited2[v]){
                    //有相邻两个节点的颜色是一样的
                    return 1;
                }
            }
            else{visited2[v] = (!visited2[u]);my_queue.push(v);}
        }
    }
    return 0;
}
void mark_knight(){
    for(int  i = 0;i < edge_count;i++){
        int u = point_dcc[i].u, v = point_dcc[i].v;
        expelled[u] = 0; expelled[v] = 0;
    }
}
int getNum(int N){
    int total = 0;//统计被踢掉的
    for(int  i = 1;i <= N;i++){
        if(expelled[i])total++;
    }
    return total;
}

void get_Point_DCC(int uu,int vv){
    //将栈中的点双连通分量弹出来
    memset(head2,-1,sizeof(head2)); edge_count = 0;
    struct edge_node p(0,0);
    do{
        p = my_deque.back();my_deque.pop_back();
        add2(p.u,p.v);
    }while(!(p.u == uu && p.v == vv));

    memset(visited2,-1,sizeof(visited2));
    if(isBipartite(point_dcc[0].u,0)){
        mark_knight();//把不需要踢掉的knight标记下
    }
}

/**
*tarjan 算法求双连通分量
*/
int dfs_order[MAX];
int lowest[MAX];
int visited[MAX];
int mark_num;
void Tarjan_DCC(int u,int father){

    dfs_order[u] = lowest[u] = mark_num++;visited[u] = 1;

    for(int i = head[u];i != -1;i = edge[i].next){
        int v = edge[i].v;
        if(!visited[v]){
            my_deque.push_back(edge_node(u,v));
            Tarjan_DCC(v,u);
            lowest[u] = mymin(lowest[u],lowest[v]);
            if(dfs_order[u] <= lowest[v]){
                get_Point_DCC(u,v);
            }
        }
        else{
            if(v != father){
                lowest[u] = mymin(lowest[u],dfs_order[v]);
                if(dfs_order[u] > dfs_order[v]){
                    my_deque.push_back(edge_node(u,v));
                }
            }
        }
    }

}
void add(int a,int b){
    edge[edge_count].u = a;
    edge[edge_count].v =  b;
    edge[edge_count].next = head[a];
    head[a] = edge_count++;
}
void init(){
    memset(graph,0,sizeof(graph));
    edge_count = 0;
    memset(head,-1,sizeof(head));
    top = 0;
    memset(visited,0,sizeof(visited));
    mark_num = 1;
    memset(expelled,1,sizeof(expelled));
    my_deque.clear();
}
///main
int main(){
    int N,M;
    while(scanf("%d%d",&N,&M) && N != 0){
        init();
        for(int i = 1;i <= M;i++){
            int a,b;scanf("%d%d",&a,&b);
            graph[a][b] = graph[b][a] = 1;
        }
        for(int  i = 1;i < N;i++){
            for(int j = i+1;j <= N;j++){
                if(graph[i][j])continue;
                add(i,j); add(j,i);//双向的边 也就是无向边
            }
        }
        for(int i = 1;i <= N;i++){
            if(visited[i])continue;
            Tarjan_DCC(i,-1);
        }
        printf("%d\n",getNum(N));

    }
    return 0;
}