tarjan求有向图的强连通分量

tarjan到底是念“塔进”还是“塔扬”。好像大多数人都念“塔进”,但是英语好像是念“塔扬”。胡扯结束。。。

这个tarjan算法求的是有向图中的强连通分量,并将他们合并。

强连通分量

(如果会可以直接看tarjan部分)那什么是强连通分量呢?强连通嘛,就是图中任意两点能相互到达。那强连通分量就是一个图中的强连通子图。

环是最简单的强连通分量:

img

那你如果从1出发,只要转一圈就能经过所有点。

强连通分量不等于环,还有一些复杂的强连通分量,例如完全图:

img

很明显能看出从图中一点出发,可到达其他任意一个点。

tarjan算法

先上时间复杂度:O(N+M) (其中N和M分别为点数和边数)

tarjan算法是通过对图的dfs来找出其中的强连通分量,并分类。(需掌握dfs的思想并且能熟练运用)

dfn数组和low数组讲解

这里给出tarjan算法中两个重要数组的定义:

​ dfn[u]:表示当前结点i在dfs算法中第几个被访问的的点。

​ low[u]:表示当前结点i能回溯到的最小dfs序结点,dfs序即dfn[u]的值

img

(6->1的箭头画反了,应该时1->6)

当从结点1开始dfs时,假设优先向下访问:dfn[1] = 1; dfn[6] = 2;因为第一个访问的时结点1,所以它的dfs序是1,第二个访问的是结点6,所以它的dfs序时2。访问完结点6发现没有路了,则开始访问结点1的下一条出边。

开始访问结点2,刚刚访问的结点6是第二个访问的结点,所以结点2是第三个访问的结点,即它的dfs序为3:dfn[2] = 3; dfn[5] = 4; dfn[4] = 5; dfn[3] = 6;我们顺着结点2依次访问下去,发现只有一条路,畅通无阻。

当访问到结点三的时候我们发现结点3有一条通向结点2的路,则此时我们称结点3回溯到结点2。我们还发现dfn[2]<dfn[3],即结点2在dfs中比结点3先被访问。此时我们在dfs回溯的过程中令:low[3] = dfn[2]; low[4] = dfn[2]; low[5] = dfn[2];即令回溯路上的所有点的low数组都赋值为结点2的dfs序。

由此我们经历了一遍tarjan的简化步骤,我们能发现low数组的取值为:

1
2
3
4
5
low[u] = min(
dfn[u],//1.
dfn[v],//2.
low[v]//3.
)
  1. low数组初始化时为当前结点的dfs序,即low[u] = dfn[u];
  2. 这里的v是边(u, v)中的v,和上图中边(3, 2)类似。当发现能回溯到的结点dfs序小于自身dfs序时更新low的值
  3. 这里的(u, v)和上图中的(4, 3)类似。dfs回溯过程中时发现前面结点的low值小于自身的low值时,更新自身low值

从图中可看出2, 5, 4, 3四个结点为一个环,环是最简单的强连通分量,所以2, 5, 4, 3为一个强连通分量。而单独一个结点我们也将他看成一个强连通分量,因此图中有三个强连通分量:(1)(6)(2,4,5,3)

从中我们观察出1, 6, 2的dfn值和low值相同,所以当dfn[u]==low[u]时,它就是一个强连通分量在dfs树中的起始节点

tarjan算法伪代码讲解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
tarjan(u)
{
DFN[u]=Low[u]=++Index//1.
Stack.push(u)//2.
for each (u, v) in E//3.
if (v is not visted)//4.
tarjan(v)//dfs
Low[u] = min(Low[u], Low[v])
else if (v in S)//5.
Low[u] = min(Low[u], DFN[v])
if (DFN[u] == Low[u])//6.
repeat
v = S.pop//7.
print v
until (u== v)
}
  1. 为结点u初始化dfn和low的值为dfs时的访问顺序,index为全局变量
  2. 将结点u压入栈中
  3. 遍历结点u的每一条边
  4. 如果没访问过
  5. 如果v在栈中
  6. 上面讲过,当dfn[u]==low[u]时,该节点为强连通分量根结点
  7. 将栈顶元素出栈,直到栈顶元素为u时,u出栈,则此次出栈的一系列元素为一个强连通分量

img

(6->1的箭头画反了,应该时1->6)

  1. 从结点1开始:dfn[1] = low[1] = 1; 结点1进栈img
  2. 1->6:dfn[6] = low[6] = 2; 结点6进栈img结点6没有出边,无法dfs,发现dfn[6]==low[6],栈顶元素出栈,栈顶元素正好时结点6,无需继续出栈,则结点6自己为一个单独的强联通分量。
  3. 1->2:dfn[2] = low[2] = 3;结点2进栈img结点2有出边且为访问,开始dfs。
  4. 2->5:dfn[5] = low[5] = 4;结点5进栈img结点5有出边且未访问,继续dfs
  5. 5->4:dfn[4] = low[4] = 5;结点4进栈img结点4有未访问的出边,继续dfs
  6. 4->3:dfn[3] = low[3] = 6;结点3进栈img结点3有出边,但结点2已经访问过了,且结点2在栈里面,所以3可以回溯到结点2,可知dfn[2]=3, low[3]=6; 所以low[3] = dfn[2] = 3;
  7. 此时dfn[3]!=low[3],所以不出栈。
  8. 当dfs回溯到5->4的时候,发现(low[4]=5) > (low[3]=3),所以low[4] = 3; 依此类推low[5]=3;且直到dfs回溯到结点2的时候才会进行出栈操作,因为2时强连通分量的根节点。
  9. 不难看出,依次出栈的时3、4、5、2,这四个结点为一个强连通分量
  10. 最后dfs回溯到最开始的入口,结点1出栈
  11. 由此的强连通分量有3个,分别是:(1)、(6)、(3,4,5,2)

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
struct Edge
{
int net;
int to;
int w;
}edge[maxn];
int head[maxn], cnt=0;//1.

void add_dege(int u, int v, int w)
{
edge[cnt].to = v;
edge[cnt].net = head[u];
edge[cnt].w = w;
head[u] = cnt++;
}

int dfn[maxn], low[maxn], belong[maxn];//2.
int index=0, Bcnt;//3.
bool instack[maxn];
stack<int> s;

void tarjan(int u)
{
dfn[u] = low[u] = ++index;
s.push(u);instack[u] = true;
for(int i=head[u]; i!=-1; i=edge[i].net)
{
int v = edge[i].to;
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[v], low[u]);
}
else if(instack[v] && dfn[v]<low[u])
low[u] = dfn[v];
}

if(dfn[u]==low[u])
{
Bcnt++;int v;
do
{
v = s.top();
s.pop();
belong[v] = Bcnt;
instack[v] = false;
}while(v!=u);
}
}

void solve()
{
Bcnt = index = 0;
memset(dfn, 0, sizeof dfn);
while(!s.empty())s.pop();
for(int i=0; i<n; i++)//4.
if(!dfn[i])//5.
tarjan(i);
}
  1. head[u]记得初始化,初始化为-1。
  2. belong数组值相同的结点属于同一个强连通分量。
  3. Bcnt用于划分强连通分量
  4. 要从每个结点都进行一次tarjan,否则有些不可达结点就无法划分强联通分量,n为结点数
  5. dfn数组初始化为0,当dfn[u]的值不为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
45
46
int mp[maxn][maxn];//1.
int dfn[maxn], low[maxn], belong[maxn];
int index=0, Bcnt;
bool instack[maxn];
stack<int> s;

void tarjan(int u)
{
dfn[u] = low[u] = ++index;
s.push(u);instack[u] = true;
for(int v=0; v<n; v++)//2.
{
if(mp[u][v]==-1)
continue;
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[v], low[u]);
}
else if(instack[v] && dfn[v]<low[u])
low[u] = dfn[v];
}

if(dfn[u]==low[u])
{
Bcnt++;
int v;
do
{
v = s.top();
s.pop();
belong[v] = Bcnt;
instack[v] = false;
}while(v!=u);
}
}

void solve()
{
Bcnt = index = 0;
memset(dfn, 0, sizeof dfn);
while(!s.empty())s.pop();
for(int i=0; i<n; i++)
if(!dfn[i])
tarjan(i);
}
  1. 邻接矩阵,当值为-1时表示不连通
  2. n为结点数

邻接表模板

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
vector<pair<int, int> > G[maxn];//1.
int dfn[maxn], low[maxn], belong[maxn];
int index=0, Bcnt;
bool instack[maxn];
stack<int> s;

void add_eage(int u, int v, int w)
{
G[u].push_back(make_pair(w, v));
//G[v].push_back(make_pair(w, u));
}

void tarjan(int u)
{
dfn[u] = low[u] = ++index;
s.push(u);instack[u] = true;
for(int i=0; i<G[u].size(); i++)
{
int v = G[u][i].second;
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[v], low[u]);
}
else if(instack[v] && dfn[v]<low[u])
low[u] = dfn[v];
}

if(dfn[u]==low[u])
{
Bcnt++;
int v;
do
{
v = s.top();
s.pop();
belong[v] = Bcnt;
instack[v] = false;
}while(v!=u);
}
}

void solve()
{
for(int i=0; i<n; i++)//2.
G[i].clear();
Bcnt = index = 0;
memset(dfn, 0, sizeof dfn);
while(!s.empty())s.pop();
for(int i=0; i<n; i++)
if(!dfn[i])
tarjan(i);
}
  1. 用vector和pair实现邻接表,pair的first为路径权重,pair的second为另一端结点
  2. 初始化邻接表

例题

HDU1269

题意:给你一个图,让你判断这个图是不是一整个强连通分量

题解:没什么可说的,tarjan模板题。需要注意的是有的能给的图只有点没有边,所以结束条件需要时m和n同时为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
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
#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5+10;

struct Edge
{
int to, net;
}edge[maxn];
int head[maxn], cnt=0;
int dfn[maxn], low[maxn], index, Bcnt, n, m, belong[maxn];
bool instack[maxn];
stack<int> s;

void addedge(int u, int v)
{
edge[cnt].to = v;
edge[cnt].net = head[u];
head[u] = cnt++;
}

void init()
{
cnt = index = Bcnt = 0;
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
memset(head, -1, sizeof head);
memset(instack, 0, sizeof instack);
memset(belong, 0, sizeof belong);
while(!s.empty())s.pop();
}

void tarjan(int u)
{
dfn[u] = low[u] = ++index;
instack[u] = true;
s.push(u);
int v;

for(int i = head[u]; i!=-1; i=edge[i].net)
{
v = edge[i].to;
if(!dfn[v])
{
tarjan(v);
if(low[v]<low[u]) low[u] = low[v];
}
else if(instack[v] && dfn[v]<low[u])
low[u] = dfn[v];
}

if(dfn[u]==low[u])
{
Bcnt++;
do
{
v = s.top();
s.pop();
belong[v] = Bcnt;
instack[v] = false;
}while(u!=v);
}
}

int main()
{
while(cin >>n >>m && n+m)
{
init();
for(int i=0; i<m; i++)
{
int u, v;
cin >>u >>v;
addedge(u, v);
}

for(int i=1; i<=n; i++)
if(!dfn[i])
tarjan(i);

int flag = belong[1];
bool f = true;
for(int i=1; i<=n; i++)
if(belong[i]!=flag)
f = false;

if(!f) cout <<"No" <<endl;
else cout <<"Yes" <<endl;
}

return 0;
}

HDU1827

题意:给你一些人的联系方式,但是这种联系方式时有向的,即x可以联系y不代表y可以联系到x,其实就是有向图。也给出你联系每个人的花费,如果可以让别人帮忙联系,就可以不需要花费话费。求最少需要联系多少人和花费多少话费。

题解:这道题没有那么直接,但是也能看出和强连通分量有关。这道题要求的是没有入边的强连通分量的个数,并且求出这些没有入边的强联通分量中花费最小的人。为什么是没有入边的强连通分量而不是强连通分量,因为有如入边的强联通分量可以被其他人通知到,就不需要你再亲自通知了。(一开始我理解成强连通分量的个数了(>_<) )这题要用scnaf和printf,不能用cin和cout,数据量大,会超时。

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
#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e4+10;
const int INF = 1<<30;

struct Edge
{
int to, net;
} edge[maxn];
int head[maxn], cnt=0;
int dfn[maxn], low[maxn], index, Bcnt, n, m, belong[maxn], fee[maxn], cost[maxn], ans;
bool instack[maxn], in[maxn];//1.
stack<int> s;

void addedge(int u, int v)
{
edge[cnt].to = v;
edge[cnt].net = head[u];
head[u] = cnt++;
}

void init()
{
cnt = index = ans = Bcnt = 0;
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
memset(head, -1, sizeof head);
memset(instack, 0, sizeof instack);
memset(belong, 0, sizeof belong);
memset(in, 0, sizeof in);
for(int i=0; i<maxn; i++)
cost[i]=INF;
memset(fee, 0, sizeof fee);
while(!s.empty())
s.pop();
}

void tarjan(int u)
{
dfn[u] = low[u] = ++index;
instack[u] = true;
s.push(u);
int v;

for(int i = head[u]; i!=-1; i=edge[i].net)
{
v = edge[i].to;
if(!dfn[v])
{
tarjan(v);
if(low[v]<low[u])
low[u] = low[v];
}
else if(instack[v] && dfn[v]<low[u])
low[u] = dfn[v];
}

if(dfn[u]==low[u])
{
Bcnt++;
do
{
v = s.top();
s.pop();
belong[v] = Bcnt;
instack[v] = false;
}
while(u!=v);
}
}

int main()
{
while(scanf("%d%d", &n, &m) != EOF)
{
init();

for(int i=1; i<=n; i++)
scanf("%d", &fee[i]);

for(int i=0; i<m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
addedge(u, v);
}

for(int i=1; i<=n; i++)
if(!dfn[i])
tarjan(i);

int cnt=Bcnt;
for(int i=1; i<=n; i++)//2.
for(int j=head[i]; j!=-1; j=edge[j].net)
if(belong[i]!=belong[edge[j].to] && !in[belong[edge[j].to]])
{
in[belong[edge[j].to]] = true;
cnt--;
}
for(int i=1; i<=n; i++)//3.
if(!in[belong[i]])
cost[belong[i]] = min(cost[belong[i]], fee[i]);

for(int i=1; i<=Bcnt; i++)
if(!in[i])
ans+=cost[i];

printf("%d %d\n", cnt, ans);
}

return 0;
}
  1. in数组表示该强连通分量是否有入边,为true则有,false则没有。
  2. 这个for循环求出有入边的强连通分量,即看看每个点的入边是否和自己在同一个强连通分量中即可。cnt为没有入边的个数。
  3. 求出没有入边的强连通分量中的最小花费,cost[i]代表第i个强连通分量的花费

参考:

  1. BYVoid有向图强连通分量的tarjan算法
Donate comment here