割点与桥

ACM

很多不知道的知识

BCC

只要存在割点,那么就会保存相应的节点信息，感觉这样和点-双联通没有什么关系。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int n, m;
int iscut[maxn], low[maxn], pre[maxn];
int bcc_cnt;
int bccno[maxn];
vector<int> bcc[maxn];
int dfs_clock;
vector<int> G[maxn];
struct Edge{
    int u, v;
};
/*
5 5
0 1
1 2
2 0
1 3
3 4
*/
stack<Edge> S;
int dfs(int u, int fa){
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;//单独判断只有一个的A---B.
    for(int i=0; i<G[u].size(); i++){
        int v = G[u][i];
        Edge e = Edge{u, v};
        if(!pre[v]){
           // printf("test:%d %d\n", e.u, e.v);
            S.push(e);
            child++;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if(lowv>=pre[u]){
                iscut[u] = 1;
                bcc_cnt++;
                bcc[bcc_cnt].clear();
                for(; ; ){
                    Edge temp = S.top();
                    S.pop();
                    if(bccno[temp.u] != bcc_cnt){
                        bcc[bcc_cnt].push_back(temp.u);
                        bccno[temp.u] = bcc_cnt;
                    }
                    if(bccno[temp.v] != bcc_cnt){
                        bcc[bcc_cnt].push_back(temp.v);
                        bccno[temp.v] = bcc_cnt;
                    }
                    if(temp.u == u &&temp.v == v) break;
                }
            }
        }
        else if(pre[v] < pre[u] && v!=fa){//判断是否为反向边
            S.push(e);
            //printf("test:%d %d\n", e.u, e.v);
            lowu = min(lowu, pre[v]);
        }
    }
    if(fa<0 &&child == 1)iscut[u] = 0;
    return lowu;
}
void find_bcc(){
    memset(pre, 0, sizeof(pre));
    memset(iscut, 0, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    dfs_clock = bcc_cnt = 0;
    for(int i=0; i<n; i++){
        if(!pre[i]) dfs(i, -1);
    }
}
int main(){
    while(~scanf("%d%d", &n, &m)){
        for(int i=0; i<n; i++) G[i].clear();
        int u, v;
        for(int i=0; i<m; i++){
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        find_bcc();
        for(int i=1; i<=bcc_cnt; i++){
            for(int j=0; j<bcc[i].size(); j++){
                printf("%d ", bcc[i][j]);
            }
            printf("\n");
        }
        printf("%d\n", bcc_cnt);
    }
    return 0;
}

图的黑白染色

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int color[maxn];
vector<int> G[maxn];
int n, m;
bool dfs(int u, int fa){
    for(int i=0; i<G[u].size(); i++){
        int v = G[u][i];
        if(v == fa) continue;
        if(!color[v]){
            color[v] = 3-color[u];
            if(!dfs(v, u)) return false;
        }
        else if(color[u] == color[v]) return false;
    }
    return true;
}
int main(){
    while(~scanf("%d%d", &n, &m)){
        for(int i=0; i<n; i++) G[i].clear();
        memset(color, 0, sizeof(color));
        int u, v;
        for(int i=0; i<m; i++){
            cin>>u>>v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        bool judge = true;
        for(int i=0; i<n; i++){
            if(!color[i]){
                color[i] = 1;
                if(!dfs(i, -1)){
                    judge = false;
                    break;
                }
            }
        }
        if(judge)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

图的奇偶染色,从而判断奇偶圈

首先定义一下偶圈：从一个初始的顶点出发，经过不重复的边，最后回到原来的点。如果经过的边数是偶数的话，那么就是偶圈。如果经过的边数是奇数的话，那么就是奇圈。

在对图进行二部染色的时候，如果这个点与之前的点的颜色相同，那么构成奇圈。
若果和前面的颜色相反的话，那么就会构成偶圈。

若两个奇圈有公共的顶点，那么这两个奇圈可以构成一个偶圈。
在下面的代码中，我们用belong[]数组来维护这个性质

题目

hdu5215

题意

判断是否存在奇圈和偶圈

题解

看上面的解析
参考来源

AC代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
vector<int> G[maxn];
int color[maxn];
int T;
int n, m;
int pre[maxn];
int belong[maxn];
int cnt;
bool even, odd;
int dfs(int u, int fa){
    for(int i=0; i<G[u].size(); i++){
        int v = G[u][i];
        if(fa == v) continue;
        if(!color[v]){
            color[v] = 3-color[u];
            pre[v] = u;
            dfs(v, u);
        }
        else if(color[u] == 3-color[v]) even = true;
        else if(color[u] == color[v]){
            odd = true;
            int temp = v;
            ++cnt;
            while(!even){
                if(temp == -1||temp == u) break;
                if(belong[temp]){
                    even = true;
                    break;
                }
                belong[temp] = cnt;
                temp = pre[temp];
            }
        }
    }
}
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        for(int i=0; i<n; i++) G[i].clear();
        int u, v;
        memset(color, 0, sizeof(color));
        memset(belong, 0, sizeof(belong));
        memset(pre, 0, sizeof(pre));
        odd = even = false;
        for(int i=0; i<m; i++){
            scanf("%d%d", &u, &v);
            G[u-1].push_back(v-1);
            G[v-1].push_back(u-1);
        }
        for(int i=0; i<n; i++){
            if(!color[i]){
                pre[i] = -1;
                color[i] = 1;
                dfs(i, -1);
            }
        }
        if(odd){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
        if(even){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }
    return 0;
}

本文标题:割点与桥

文章作者:Babydragon

发布时间:2018-03-08, 20:04:40

最后更新:2018-03-23, 13:31:50

原始链接:http://baolintian.github.io/2018/03/08/割点与桥/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. BCC
  2. 2. 图的黑白染色
  3. 3. 图的奇偶染色,从而判断奇偶圈
    1. 3.1. 题目
    2. 3.2. 题意
    3. 3.3. 题解
    4. 3.4. AC代码
{{ live2d() }}