la3523 白书例题 圆桌骑士 双联通分量+二分图

具体题解看大白书P316

#include <iostream>

#include <algorithm>

#include <vector>

#include <string.h>

#include <stack>

#include <cstdio>

using namespace std;

struct Edge{int u,v;};

const int maxn = +;

int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cnt;

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

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]){ // v没有访问过

            S.push(e);

            child++;

            int lowv=dfs(v,u);

            lowu = min(lowu,lowv);// 用后代的 low函数更新自己

            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[u] == color[v]) return false;

        if(!color[v]){

             color[v]= - color[u];

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

        }

    }

     return true;

}

int A[maxn][maxn];

int main()

{

    int kase=, 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 ;

}