UVA1364 Knights of the Round Table | 点双连通分量

主要就是一个性质：如果一个点双连通分量中有奇环，那么这个点双连通分量中的每个点都在至少一个奇环中。

# include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n,m;
bool w[N][N];
vector <int> g[N];
int dfn[N],low[N],dfntot = 0,s[N],top = 0,belong[N],cnt = 0;
vector <int> dcc[N];
int c[N];
bool Cut[N],F[N];
void tarjan(int x,int fa)
{
    dfn[x] = low[x] = ++dfntot;
    s[++top] = x;
    for(int i = 0; i < (int)g[x].size(); i++)
    {
        int v = g[x][i];
        if(v == fa) continue;
        if(!dfn[v])
        {
            tarjan(v,x);
            low[x] = min(low[x],low[v]);
            if(low[v] >= dfn[x])
            {
                ++cnt;
                dcc[cnt].push_back(x); int vv;
                do
                {
                    vv = s[top--];
                    dcc[cnt].push_back(vv);
                }while(vv != v);
            }
        }
        else low[x] = min(low[x],dfn[v]);
    }
    return;
}
bool dfs(int x,int col)
{
    c[x] = col;
    bool flag = 0;
    for(int i = 0; i < (int)g[x].size(); i++)
    {
        int v = g[x][i];
        if(belong[v] != belong[x]) continue;
        if(c[v] > 0 && c[v] == c[x]) return 1;
        else if(c[v] == 0) flag |= dfs(v,3 - col);
    }   
    return flag;
}
int main(void)
{
    while(~scanf("%d%d",&n,&m) && n)
    {
        for(int i = 1; i <= n; i++) 
        {
            for(int j = 1; j <= n; j++) w[i][j] = 0;
            g[i].clear();dcc[i].clear();
            dfn[i] = low[i] = c[i] = belong[i] = 0;
            F[i] = 0;
        }
        dfntot = 0,cnt = 0,top = 0;
        for(int i = 1; i <= m; i++) 
        {
            int u,v; scanf("%d%d",&u,&v);
            w[u][v] = w[v][u] = 1;
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = i + 1; j <= n; j++)
            {
                if(!w[i][j])
                {
                    g[i].push_back(j),g[j].push_back(i);
                }
            }
        }
        for(int i = 1; i <= n; i++) if(!dfn[i]) top = 0,tarjan(i,0);
        for(int i = 1; i <= cnt; i++)
        {
            // printf("dcc:%d\n",i);
            for(int j = 0; j < (int)dcc[i].size(); j++)
            {
                belong[dcc[i][j]] = i; c[dcc[i][j]] = 0;
            }
            // printf("\n");
            int ro = dcc[i][0];
            if(dfs(ro,1)) 
            {
                for(int j = 0; j < (int)dcc[i].size(); j++)
                {
                    F[dcc[i][j]] = 1;
                }
            }
        }
        int ans = 0;
        for(int i = 1; i <= n; i++) if(!F[i]) ++ans;
        printf("%d\n",ans);
    }

    return 0;
}