有向图的强连通分支之Tarjan算法

缘起

在【1】中，我们给出了O(n+e)复杂度的求有向图的强连通分支的算法. 这是我对严蔚敏奶奶书上描述的算法实现. 而竞赛圈用的更多的是tarjan、gabow、kasaraju 等算法. 本文介绍的就是tarjan算法.

分析

tarjan 算法的核心是收割. 就是建立一个low数组表示最早该顶点能回到的顶点，如果一致的话, 就表示出现了强连通分支， 然后就收割. 

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
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#pragma warning(disable:4996)

#define LOCAL
using namespace std;
const int MAX_NUM = 20;
typedef vector<int>::iterator it;

struct Graph
{
	vector<int> vertex[MAX_NUM];
	int n;
	vector<int> scc[MAX_NUM]; // 强连通分支
	stack<int> s;
	bool isInstack[MAX_NUM]; // 是否还在栈中, 是的话, 表示已经搜索到, 但是尚未处理(即比较low和timestamp)， isInstack[i]=  true 表示i号顶点尚在栈中
	int timestamp[MAX_NUM]; // 时间戳 timestamp[i] = j 表示i号顶点在j时刻被搜索到（被发现）
	int low[MAX_NUM]; // low[i] = j 表示i号顶点最早可以回到时刻j 被搜索到的顶点
	int index; // 搜索的顺序.(可以理解为时间)
	int sccnum; // 强连通分支的个数

	Graph()
	{
		sccnum = index = 0;
		memset(isInstack, 0, sizeof(isInstack));
		memset(timestamp, 0, sizeof(timestamp));
		memset(low, 0, sizeof(low));
		puts("输入顶点的实际个数.");
		scanf("%d", &n);
		puts("输入边, 起点在前, 终点在后.");
		int start, end;
		while(~scanf("%d%d", &start, &end)) vertex[start].push_back(end);
	}

	// 获取有向图的强连通分支
	void getscc() {for (int i = 0; i<n;i++) if (!timestamp[i]) tarjan(i);}; // 只对尚未被发现的点运行tarjan}

private:

	void tarjan(int i) // i是当前搜索的顶点
	{
		timestamp[i] = low[i] = ++index; // 顶点i在++index时刻被发现.
		s.push(i);
		isInstack[i] = true;
		for (it x = vertex[i].begin(); x!=vertex[i].end(); x++)
		{
			if (!timestamp[*x]) // 如果 i->*x是树边, 即*x是刚被发现
			{
				tarjan(*x);
				low[i] = min(low[i], low[*x]); // 使用*x更新自己的low
			}
			else if(isInstack[*x]) // 虽然已经被发现过了, 但是还在栈中, 这种情况是存在的, 就是1->2->3->4 而 4->2 是存在的. 4在试探的时候不会走上面的if，而会走这里的代码
			{
				low[i] = min(low[i], low[*x]); // 使用*x更新自己的low
			}
		} // 此for循环结束之后, 要从i推出递归. 此时就要算账了.
		if (low[i]==timestamp[i]) // 表明i往后的栈中的元素就都是包含i的scc中的顶点了,因为栈里面i之后的都是从i出发搜出来的, 注意, 一定是强连通的. 不肯能后面的只会回到i之后的某个顶点, 因为这样的话, 它们早就被收割掉了
		{
			int j;
			do 
			{
				j = s.top();
				s.pop();
				scc[sccnum].push_back(j);
				isInstack[j] = false; // 不再在栈中了 这个必须要改为false, 不然会影响上面的 else if(isInstack[*x])
			} while (j!=i); // 最后i也会被弹出去的.
			sccnum++;
		}
	}
};

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif

	Graph g;
	g.getscc();
	printf("一共%d个强连通分支\n", g.sccnum);
	for (int i = 0; i< g.sccnum; i++)
	{
		for (it x = g.scc[i].begin(); x!=g.scc[i].end(); x++)
		{
			printf("%d ", *x);
		}
		puts("");
	}
	return 0;
}
/*
测试数据
5
4 0
0 1
3 1
3 0
0 2
2 3
3 2
2 0
*/

关于tarjan算法进一步的形象论述参见【2】

参考

【1】https://yfsyfs.github.io/2019/05/22/%E6%9C%89%E5%90%91%E5%9B%BE%E7%9A%84%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E6%94%AF%E4%B9%8B%E6%9C%B4%E7%B4%A0%E6%B1%82%E6%B3%95-%E5%88%A9%E7%94%A8%E6%B7%B1%E6%90%9C/

【2】https://yfsyfs.github.io/2019/09/07/POJ-2186-Popular-Cows-scc%E7%9A%84%E4%B8%89%E7%A7%8D%E5%A7%BF%E5%8A%BF/