poj 2942 Knights of the Round Table 点重联通分量

  书上把这放在边联通的第一道题，于是一开始就按边写了，一直写不对，重新想了一遍，才发现是点联通……

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#define pb push_back
using namespace std;
int n,m;
int Map[1005][1005];
vector<int> org[1005];
vector<int> belong[1005];
int vis[1005];
int dph[1005],low[1005];
int d;
int num=0;
bool ok[1005];
stack<int> S;
void dfs(int v,int f)
{
    vis[v]=1;
    dph[v]=low[v]=d++;
    S.push(v);
    for(int i=0; i<org[v].size(); i++)
    {
        int u=org[v][i];
        if(u==f)continue;
        if(vis[u]==1)low[v]=min(low[v],dph[u]);
        else if(!vis[u])
        {
            dfs(u,v);
            low[v]=min(low[v],low[u]);
            if(low[u]>=dph[v])
            {
                num++;
                belong[v].pb(num);
                belong[u].pb(num);
                while(S.top()!=u)// 注意边界，如果吧push放在for循环里就是!=v不用pop，否则就是!=u最后还要pop
                {
                    belong[S.top()].pb(num);
                    S.pop();
                }
                S.pop();
            }
        }
    }
    vis[v]=2;
}
int Tarjan() //搜索重联通分量
{
    num=0;
    while(!S.empty())S.pop();
    for(int i=1; i<=n; i++)
    {
        d=0;
        if(!vis[i])
            dfs(i,-1);
    }
}
int dye(int v,int c,int flag)//1,-1染色
{
    vis[v]=c;
    for(int i=0; i<org[v].size(); i++)
    {
        int &u=org[v][i];
        if(ok[u])
        {
            if(vis[u]==0&&dye(u,-c,flag))return 1;
            if(vis[u]==c)return 1;
        }
    }
    return 0;
}
int use[1005];
int Count()
{
    int ans=0;

    memset(use,0,sizeof(use));
    for(int k=1; k<=num; k++)
    {
        memset(ok,0,sizeof(ok));
        memset(vis,0,sizeof(vis));
        for(int i=1; i<=n; i++)
        {
            if(find(belong[i].begin(),belong[i].end(),k)!=belong[i].end())
                ok[i]=1;
        }
        for(int i=1; i<=n; i++)
        {
            if(ok[i])
            {
                if(dye(i,1,k))
                    for(int j=1; j<=n; j++)
                        use[j]+=ok[j];
                break;
            }
        }
    }
    for(int i=1; i<=n; i++)
        if(!use[i])ans++;
    return ans;
}
int main()
{
    while(~scanf("%d%d",&n,&m)&&n+m)
    {
        int a,b;
        int i,j;
        memset(vis,0,sizeof(vis));
        memset(Map,0,sizeof(Map));
        for(i=1; i<=n; i++)
        {
            org[i].clear();
            belong[i].clear();
            Map[i][i]=1;
        }
        for(i=0; i<m; i++)
        {
            scanf("%d%d",&a,&b);
            Map[a][b]=Map[b][a]=1;
        }
        for(i=1; i<=n; i++) //建立不憎恨的图
        {
            for(j=i; j<=n; j++)
                if(!Map[i][j])
                {
                    org[i].pb(j);
                    org[j].pb(i);
                }
        }
        Tarjan();
        printf("%d\n",Count());
    }
}