Tarjan算法求强联通分量

Tarjan算法简介

由Robert Tarjan提出的求解有向图强连通分量的算法,它能做到线性时间的复杂度。O(E+V)

算法描述

待补充

参考链接: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
/*
有向图
输入n,m => n个结点,m条边
求该有向图的联通分量

联通分量: 任意结点两两可达的有向图子图
*/
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a; i<=b; ++i)
#define per(i,b,a) for(int i=b; i>=a; --i)
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ms(a, b) memset(a, b, sizeof(a))
#define de(a) cout <<#a <<" => "<<a<<endl
#define dep(a, b) cout <<"("<<a<<","<<b<<")"<<endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int>vi;

const int maxn = 1e5+7;
int n , m;
// --------- 此处建边 ------------
struct edge{
int v, nx;
}e[maxn<<1]; // 邻接表
int fi[maxn], id=0; //fi需要初始化为-1
void adde(int u, int v) {
e[id].v = v;
e[id].nx = fi[u];
fi[u] = id++;
}
int belong[maxn], ans=0;

// -----------此处描述 Tarjan 算法------------
int dfn[maxn], sig=0;
// dfn[i]表示 编号为i的结点在DFS中被搜索到的时间戳(第 dfn[i] 个被搜索)

int low[maxn];
// low[i]表示 i或i的子树能够追溯到的最早的栈中节点的次序号

int _stack[maxn], top=0;
// 模拟栈,用于回溯记录联通分量
bool ins[maxn];
// 是否在栈中

void Tarjan(int u) {
dfn[u] = ++sig; //dfn[u]保持不变, low[u]根据所能到达的点而改变
low[u] = sig;
_stack[++top] = u;
ins[u] = true;
for(int i=fi[u]; ~i; i=e[i].nx) {
int v = e[i].v;
if(dfn[v] == 0) {
Tarjan(v);
low[u] = min(low[u], low[v]);
} else if(ins[v]) {
low[u] = min(low[u], dfn[v]);
}
}
/*--------------------------------------------
遍历过的子树,所处的low[u]=根节点且dfn[u]>根节点次序
唯有在根节点处, 遍历完根节点所有的边后, low[根节点]=根节点次序
即dfn[u] = low[u]
------------------------------------------------------*/
if(low[u] == dfn[u]) {
++ans;
printf("第%d个联通分量 : ", ans);
int j = -1;
while(j!=u && top) {
j = _stack[top--];
ins[j] = false;
belong[j] = ans;
printf("%d ", j);
}
puts("");
}
}
// ------------ 初始化函数 -------------------
void init(){
ms(fi, -1), id=0; //邻接表初始化
ms(ins, false);
}
// ------------ 主函数 ----------------------
int main(){
init();
int u,v;
scanf("%d%d", &n, &m);
rep(i, 1, m) {
scanf("%d%d", &u, &v);
adde(u, v); // u -> v;
}
Tarjan(1);
printf("联通分量数目 => %d \n", ans);
return 0;
}