POJ 2942 圆桌骑士

之前做过这个题目，现在回想起来，又有新的柑橘。

求必须出去的骑士人数。

每一个双连通分量，如果是一个奇圈，那么一定是二分图染色失败。

依次遍历每个双连通分量，但是，对于邻接表中，有一些点不是双连通分量里面的，于是要重新编号bccno，因为割点bccno只有一个值，

但是，他要多次使用，因此要重新编号bccno

#include <cstdio>

#include <cstring>

#include <stack>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn =  + ;

int pre[maxn];

bool iscut[maxn];

int bccno[maxn];

int dfs_clock;

int bcc_cnt;

vector<int> G[maxn],bcc[maxn];

struct Edge

{

    int u,v;

    Edge(int u=,int v=) : u(u),v(v) {}

};

stack <Edge> S;

int dfs(int u, int fa)

{

    int lowu = pre[u] = ++dfs_clock;

    int child = ;

    for(int i = ; i < G[u].size(); i++)

    {

        int v = G[u][i];

        Edge e = (Edge){u,v};

        if(!pre[v])

        {

            S.push(e);

            child++;

            int lowv = dfs(v, u);

            lowu = min(lowu, lowv);

            if(lowv >= pre[u])

            {

                iscut[u] = true;

                bcc_cnt++;

                bcc[bcc_cnt].clear();

                for(;;)

                {

                    Edge x = S.top();

                    S.pop();

                    if(bccno[x.u] != bcc_cnt)

                    {

                        bcc[bcc_cnt].push_back(x.u);

                        bccno[x.u] = bcc_cnt;

                    }

                    if(bccno[x.v] != bcc_cnt)

                    {

                        bcc[bcc_cnt].push_back(x.v);

                        bccno[x.v] = bcc_cnt;

                    }

                    if(x.u == u && x.v == v) break;

                }

            }

        }

        else if(pre[v] < pre[u] && v != fa)

        {

            S.push(e);

            lowu = min(lowu, pre[v]);

        }

    }

    if(fa <  && child == ) iscut[u] = ;

    return lowu;

}

void find_bcc(int n)

{

    memset(pre, , sizeof(pre));

    memset(iscut, , sizeof(iscut));

    memset(bccno, , sizeof(bccno));

    dfs_clock = bcc_cnt = ;

    for(int i = ; i < n; i++)

        if(!pre[i]) dfs(i, -);

}

int odd[maxn], color[maxn];

bool bipartite(int u, int b)

{

    for(int i = ; i < G[u].size(); i++)

    {

        int v = G[u][i];

        if(bccno[v] != b) continue;

        if(color[v] == color[u]) return false;

        if(!color[v])

        {

            color[v] =  - color[u];

            if(!bipartite(v, b)) return false;

        }

    }

    return true;

}

int A[maxn][maxn];

int main()

{

    int  n, m;

    while(scanf("%d%d", &n, &m) ==  && n)

    {

        for(int i = ; i < n; i++) G[i].clear();

        memset(A, , sizeof(A));

        for(int i = ; i < m; i++)

        {

            int u, v;

            scanf("%d%d", &u, &v);

            u--;

            v--;

            A[u][v] = A[v][u] = ;

        }

        for(int u = ; u < n; u++)

            for(int v = u+; v < n; v++)

                if(!A[u][v])

                {

                    G[u].push_back(v);

                    G[v].push_back(u);

                }

        find_bcc(n);

        memset(odd, , sizeof(odd));

        for(int i = ; i <= bcc_cnt; i++)

        {

            memset(color, , sizeof(color));

            for(int j = ; j < bcc[i].size(); j++)

                bccno[bcc[i][j]] = i;

            int u = bcc[i][];

            color[u] = ;

            if(!bipartite(u, i))

            {

                for(int j = ; j < bcc[i].size(); j++)

                    odd[bcc[i][j]] = ;

            }

        }

        int ans = n;

        for(int i = ; i < n; i++)

            if(odd[i])

                ans--;

        printf("%d\n", ans);

    }

    return ;

}