kuangbin专题9--连通图

ACM

一些图论算法
专题链接：专题九-连通图

A

题解

缩点后，任务A为求缩点后的图中入度为0的点。
任务B为入度为0，和出度为0的点数的最大值。

注意最后缩为一个点的时候任务B要特判！

晚上学一下tarjan的缩点的方法。

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
106
107
108
109
110
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 1e2+10;
vector<int> G[maxn];
vector<int> rG[maxn];
vector<int> new_G[maxn];
bool link[maxn][maxn];
int in[maxn];
int out[maxn];
int n;
int belong[maxn];
bool vis[maxn];
vector<int> vs;
void init(){
    for(int i=0; i<maxn; i++) G[i].clear();
    for(int i=0; i<maxn; i++) rG[i].clear();
    for(int i=0; i<maxn; i++) new_G[i].clear();
    memset(vis, 0, sizeof(vis));
    memset(in, 0, sizeof(in));
    memset(out, 0, sizeof(out));
}
void dfs(int u){
    vis[u] = true;
    for(int i=0; i<G[u].size(); i++){
        int v = G[u][i];
        if(vis[v]) continue;
        else dfs(v);
    }
    vs.push_back(u);
}
void rdfs(int u, int k){
    vis[u] = true;
    belong[u] = k;
    for(int i=0; i<rG[u].size(); i++){
        int v = rG[u][i];
        if(vis[v]) continue;
        rdfs(v, k);
    }
}
int scc(){
    vs.clear();
    memset(vis, 0, sizeof(vis));
    for(int i=1; i<=n; i++){
        if(!vis[i]) dfs(i);
    }
    memset(vis, 0, sizeof(vis));
    int k=0;
    for(int i=vs.size()-1; i>=0; i--){
        int u = vs[i];
        if(!vis[u]) rdfs(u, k++);
    }
    return k;
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n){
        init();
        for(int i=1; i<=n; i++){
            int u;
            while(cin>>u&&u){
                G[i].push_back(u);
                rG[u].push_back(i);
            }
        }
        int sz = scc();
        memset(link, 0, sizeof(link));
        for(int i=1; i<=n; i++){
            for(int j=0; j<G[i].size(); j++){
                int u = i;
                int v = G[i][j];
                if(belong[u]!=belong[v]&&!link[belong[u]][belong[v]]) {
                    new_G[belong[u]].push_back(belong[v]);
                    link[belong[u]][belong[v]] = true;
                }
            }
        }
        for(int i=0; i<sz; i++){
            for(int j=0; j<new_G[i].size(); j++){
                int v = new_G[i][j];
                in[v]++;
                out[i]++;
            }
        }
        if(sz == 1){
            printf("1\n0\n");
            continue;
        }
        int ans1 = 0;
        int ans2 = 0;
        for(int i=0; i<sz; i++){
            if(in[i] == 0) ans1++;
            if(out[i] == 0) ans2++;
        }
        cout<<ans1<<endl;
        cout<<max(ans1, ans2)<<endl;
    }
    return 0;
}

B

一道很裸的求无向图的割点的个数。

AC代码

cut数组没有初始化，导致wa了两发

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
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e2+10;
const int maxm = 1e4;
int n;
struct Edge{
    int v, next;
    bool cut;
}edge[maxm];
int head[maxn];
int tot;
int low[maxn], dfn[maxn], Stack[maxn];
int Index, top;
bool instack[maxn];
bool cut[maxn];
int add_block[maxn];
int bridge;
bool vis[maxn];
void add_edge(int u, int v){
    edge[tot].v = v;
    edge[tot].next = head[u];
    edge[tot].cut = true;
    head[u] = tot++;
}
void tarjan(int u, int fa){
    low[u] = dfn[u] = ++Index;
    int son = 0;
    for(int i = head[u]; ~i; i=edge[i].next){
        int v = edge[i].v;
        if(v == fa) continue;
        if(!dfn[v]){
            son++;
            tarjan(v, u);
            if(low[v]<low[u]) low[u] = low[v];
            if(low[v]>dfn[u]){
                bridge++;
                edge[i].cut = true;
                edge[i^1].cut = true;
            }
            if(low[v]>=dfn[u]&&fa!=-1){
                cut[u] = true;
                add_block[u]++;
            }
        }
        else if(low[u]>dfn[v]){
            low[u] = dfn[v];
        }
    }
    if(son>1&&fa == -1) cut[u] = true;
    if(fa == -1) add_block[u] = son-1;
}
void init(){
    memset(head, -1, sizeof(head));
    memset(instack, 0, sizeof(instack));
    tot = 0;
    bridge = 0;
    top = Index = 0;
    memset(add_block, 0, sizeof(add_block));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(cut, 0, sizeof(cut));
}
int main()
{
    ios::sync_with_stdio(false);
    while(scanf("%d",&n),n)
    {
        int a,b;
        char ch;
        init();
        while(scanf("%d",&a),a)
        {
            while(scanf("%d%c",&b,&ch))
            {
                add_edge(a, b);
                add_edge(b, a);
                if(ch=='\n')
                    break;
            }
        }
        tarjan(1, -1);
        int ans = 0;
        for(int i=1; i<=n; i++){
            if(cut[i]){
                ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

曹操的桥

题解

找到一个桥，且它的权重最小
需要注意以下的几点：

  1. 桥的权重可能为0，这个时候派出的人数为1.
  2. 会有重边的存在
  3. 当其中的图已经不连通的时候，直接输出0.
  4. 当图中不存在桥的时候，输出-1.
    因为有重边的存在。
    将
    1
    if(v == fa) continue;

改成

1
2
3
4
5
if(v == fa) {
    if(cnt) low[u] = dfn[v];//防止将此边当成是桥：low[v]>dfn[u]
    cnt++;
    continue;
}

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
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e3+10;
const int maxm = 1e6+10;
const int INF = 1e9;
int n, m;
struct Edge{
    int v, next, weight;
    bool cut;
}edge[maxm];
int head[maxn];
int tot;
int low[maxn], dfn[maxn], Stack[maxn];
int Index, top;
bool instack[maxn];
bool cut[maxn];
int add_block[maxn];
int bridge;
void add_edge(int u, int v, int weight){
    edge[tot].v = v;
    edge[tot].next = head[u];
    edge[tot].weight = weight;
    edge[tot].cut = false;
    head[u] = tot++;
}
int G[maxn][maxn];
bool vis[maxn][maxn];
bool is_chong[maxn][maxn];
void tarjan(int u, int fa){
    int v;
    low[u] = dfn[u] = ++Index;
    int son = 0;
    int cnt = 0;
    for(int i = head[u]; ~i; i=edge[i].next){
        v = edge[i].v;
        if(v == fa) {
            if(cnt) low[u] = dfn[v];
            cnt++;
            continue;
        }
        if(!dfn[v]){
            son++;
            tarjan(v, u);
            if(low[v]<low[u]) low[u] = low[v];
            if(low[v]>dfn[u]){
                bridge++;
                edge[i].cut = true;
                edge[i^1].cut = true;
            }
            if(low[v]>=dfn[u]&&fa!=-1){
                cut[u] = true;
                //if(u == 1) cout<<"yes"<<endl;
                add_block[u]++;
            }
        }
        else if(low[u]>dfn[v]){
            low[u] = dfn[v];
        }
    }
    if(son>1&&fa == -1) cut[u] = true;
    if(fa == -1) add_block[u] = son-1;
}
void init(){
    memset(head, -1, sizeof(head));
    memset(instack, 0, sizeof(instack));
    tot = 0;
    bridge = 0;
    top = Index = 0;
    memset(add_block, 0, sizeof(add_block));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(cut, 0, sizeof(cut));
    memset(vis, 0, sizeof(vis));
    memset(is_chong, 0, sizeof(is_chong));
    for(int i=0; i<maxn; i++)
        for(int j=0; j<maxn; j++) G[i][j] = -1;
}
int min1(int a, int b){
    if(a == -1) return b;
    else if(b == -1) return  a;
    else if(a>b) return b;
    else return a;
}
int main()
{
    while(cin>>n>>m&&(n+m)){
        init();
        int u, v, weight;
        for(int i=0; i<m; i++){
            cin>>u>>v>>weight;
            add_edge(u, v, weight);
            add_edge(v, u, weight);
            if(vis[u][v]) {
                is_chong[u][v] = true;
                is_chong[v][u] = true;
            }
            vis[u][v] = vis[v][u] = true;
        }
        tarjan(1, -1);
        bool flag = false;
        for(int i=1; i<=n; i++){
            if(dfn[i] == 0){
                flag = true;
                cout<<"0"<<endl;
                break;
            }
        }
        if(flag) continue;
        if(bridge == 0) {
            cout<<"-1"<<endl;
        }
        else{
            int ans = INF;
            for(int i=1; i<=n; i++){
                for(int j=head[i]; ~j; j = edge[j].next){
                    int u =i;
                    int v = edge[j].v;
                    if(edge[j].cut == true&&(!is_chong[u][v])&&(!is_chong[v][u])){
                        G[u][v] = edge[j].weight;
                        G[v][u] = edge[j].weight;
                    }
                    else if((edge[j].cut == true)&&(is_chong[u][v])){
                        G[u][v] = -1;
                        G[v][u] = -1;
                    }
                }
            }
            for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++){
                if(i == j) continue;
                if(is_chong[i][j]){
                    G[i][j] = G[j][i] = -1;
                }
            }
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    if(j == i) continue;
                    else{
                        ans = min1(ans, G[i][j]);
                    }
                }
            }
            if(ans == 0) ans++;
            cout<<ans<<endl;
        }
    }
    return 0;
}

未解决的问题

本文标题:kuangbin专题9--连通图

文章作者:Babydragon

发布时间:2018-04-30, 17:42:46

最后更新:2018-05-01, 21:25:26

原始链接:http://baolintian.github.io/2018/04/30/kuangbin专题9-连通图/

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

文章目录
  1. 1. A
    1. 1.1. 题解
  2. 2. B
    1. 2.1. AC代码
  3. 3. 曹操的桥
    1. 3.1. 题解
    2. 3.2. AC代码
  4. 4. 未解决的问题
{{ live2d() }}