scc

scc模板

原理

求解强联通块的时候,运用两次dfs

  1. 第一次dfs的时候求出后序遍历的顺序。
  2. 第二次dfs的时候通过反向图,求出每一个连通块。

题目

poj 2186Popular Cows

题意

  • 若A认为B是红牛,B认为C是红牛,那么A也认为C是红牛。这样具有传递的关系。
  • 求出被所有的牛公认的红牛的个数。

题解

  • 一个强联通块内,所有牛都相互认为是红牛。
  • 有向图中,最后一个强联通块内的红牛被公认为红牛。因此只需要求最后一个强联通块内牛的只数就行了
  • 最后注意判断是否有不连通的情况,即从最后一个块中的红牛出发,反向遍历整张图,看是否所有的点都可达。

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
/*
12 16
12 11
11 8
11 10
8 10
10 9
9 8
9 7
7 6
6 5
5 7
6 3
6 4
4 3
3 2
2 3
4 1
*/
using namespace std;
const int maxn = 1e4+10;
vector<int> G[maxn];
vector<int> rG[maxn];
bool vis[maxn];
int index[maxn];
vector<int> vs;
void add_edge(int u, int v){
G[u].push_back(v);
rG[v].push_back(u);
}
int n, m;
void dfs(int u){
vis[u] = true;
for(int i=0; i<G[u].size(); i++){
if(!vis[G[u][i]]) dfs(G[u][i]);
}
vs.push_back(u);
}
void rdfs(int v, int k){
vis[v] = true;
index[v] = k;
for(int i=0; i<rG[v].size(); i++){
if(!vis[rG[v][i]])rdfs(rG[v][i], k);
}
}
int scc(){
memset(vis, 0, sizeof(vis));
vs.clear();
for(int i=0; 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--){
if(!vis[vs[i]]){
rdfs(vs[i], k++);
}
}
int u=-1;
int ans = 0;
for(int i=0; i<n; i++){
if(index[i] == k-1){
u = i;
ans++;
}
}
memset(vis, 0, sizeof(vis));
rdfs(u, 0);
for(int i=0; i<n; i++){
if(!vis[i]){
ans = 0;
break;
}
}
printf("%d\n", ans);
}
int main()
{
while(~scanf("%d%d", &n, &m)){
for(int i=0; i<n; i++){
G[i].clear();
rG[i].clear();
}
int u, v;
for(int i=0; i<m; i++){
scanf("%d%d", &u, &v);
add_edge(u-1, v-1);
}
scc();
}
return 0;
}

tarjan算法来求有向图的强联通分量

时间复杂度是线性的,常数比前面的Kosaraju的算法小一点,所以更推荐这个算法

算法的思想和求割点有点像

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int pre[maxn], low[maxn], sccno[maxn];
int dfs_clock, scc_cnt;
vector<int> G[maxn];
int n, m;
stack<int> S;
void dfs(int u){
pre[u] = low[u] = ++dfs_clock;
S.push(u);
for(int i=0; i<G[u].size(); i++){
int v = G[u][i];
if(!pre[v]){
dfs(v);
low[u] = min(low[u], low[v]);
}
else if(!sccno[v]){
low[u] = min(low[u], pre[v]);
}
}
if(low[u] == pre[u]){
++scc_cnt;
while(!S.empty()){
int temp = S.top();
S.pop();
sccno[temp] = scc_cnt;
if(temp == u) break;
}
}
}
void find_scc(){
memset(pre, 0 ,sizeof(pre));
memset(low, 0, sizeof(low));
memset(sccno, 0, sizeof(sccno));
dfs_clock = scc_cnt = 0;
for(int i=0; i<n; i++){
if(!pre[i]){
dfs(i);
}
}
}
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-1].push_back(v-1);
}
find_scc();
for(int i=0; i<n; i++){
printf("%d ", sccno[i]);
}
printf("\n");
}
return 0;
}

未解决的问题

如何进行相应的缩点。
能进行释放点吗?
有时间学习一波tarjan的算法tarjan算法求有向图的强联通分量

文章目录
  1. 1. 原理
  2. 2. 题目
    1. 2.1. 题意
    2. 2.2. 题解
    3. 2.3. AC 代码
  3. 3. tarjan算法来求有向图的强联通分量
  4. 4. 未解决的问题
{{ live2d() }}