UVALive3523 (Knights of the Round Table)[点双连通分量]

发表于 | 更新于 | | 阅读次数：

题目链接

本题可以转化为求不在任何一个简单奇圈上的结点个数。
简单圈上的所有结点必然属于一个点双连通分量。因此需要先找出所有双连通分量，二分图是没有奇圈的，因此我们只需要关注那些不是二分图的双连通分量，可以证明这些双连通分量一定都在某个奇圈上。
对于每个连通分量的每个双连通分量B，若它不是二分图，给B中所有结点标记为“在奇圈上”。注意，由于每个割顶属于多个双连通分量，它可能被标记多次。
引用自刘汝佳《算法竞赛入门经典 训练指南》

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int maxn=1009;
int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cnt;
vector<int> G[maxn],bcc[maxn];
struct Edge {
    int u,v;
};
stack<Edge> S;

int dfs(int u,int fa) {
    int lowu=pre[u]=++dfs_clock;
    int child=0;
    for(int i=0;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();
                while(true) {
                    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<0 && child==1) iscut[u]=0;
    return lowu;
}
void find_bcc(int n) {
    memset(pre,0,sizeof(pre));
    memset(iscut,0,sizeof(iscut));
    memset(bccno,0,sizeof(bccno));
    dfs_clock=bcc_cnt=0;
    for(int i=1;i<=n;i++) {
        if(!pre[i]) dfs(i,-1);
    }
}
bool hate[maxn][maxn];
int n,m;
int col[maxn];
bool ok[maxn];

bool is_bipartite(int u,int b) {
    int v;
    for(int i=0;i<G[u].size();i++) {
        v=G[u][i];
        if(bccno[v]!=b) continue;
        if(col[v]==col[u]) return false;
        if(!col[v]) {
            col[v]=3-col[u];
            if(!is_bipartite(v,b)) return false;
        }
    }
    return true;
}

int main() {
    int u,v;
    while(~scanf("%d%d",&n,&m)) {
        if(n==0 && m==0) break;
        memset(hate,0,sizeof(hate));
        for(int i=1;i<=n;i++) G[i].clear();
        for(int i=0;i<m;i++) {
            scanf("%d%d",&u,&v);
            hate[u][v]=hate[v][u]=1;
        }
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++) {
                if(!hate[i][j]) {
                    G[i].push_back(j);
                    G[j].push_back(i);
                }
            }
        find_bcc(n);
        memset(ok,0,sizeof(ok));
        for(int i=1;i<=bcc_cnt;i++) {
            memset(col,0,sizeof(col));
            for(int j=0;j<bcc[i].size();j++) bccno[bcc[i][j]]=i;
            int u=bcc[i][0];
            col[u]=1;
            if(!is_bipartite(u,i))
                for(int j=0;j<bcc[i].size();j++) ok[bcc[i][j]]=true;
        }
        int ans=n;
        for(int i=1;i<=n;i++)
            if(ok[i]) ans--;
        printf("%d\n",ans);
    }
}