图的割点-tarjan算法求图的割点

在无向连通图中讨论

核心思想：

  • 用num数组来存储每个顶点被访问的时间戳
  • 用low数组来存储每个顶点 所能回溯的 最早被访问的顶点的时间戳，是不断更新的
  • 如果存在一个顶点i，i是当前顶点cur的孩子，且low[i]>=num[cur]，即i在不通过父节点（即cur）的情况下最多只能回溯到cur，则cur为一个割点**（cur不是根节点的情况下）**
  • 如果cur为根节点，则如果cur有两个或以上的孩子节点，则cur为割点

示例问题

一场大战即将打响，我们已经收集到敌人城市的地图，希望炸毁其中一座城市，使得剩下的城市中间不能两两互通。数据给出格式如下：

1
2
3
4
5
6
7
8
6 7
1 4
1 3
4 2
3 2
2 5
2 6 
5 6

第一行两个数字a，b：表示有a座城市，b条路径

接下来b行，每行两个数字u，v：表示u城到v城之间有路径

整体代码

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
#include<iostream>
using namespace std;

int point, edge;//点数和边数
int root = 1;//默认根节点为1
int index = 0;

void dfs(bool* flag,int* num,int* low,int** arr,int cur, int father)
{
	int child = 0;//记录孩子节点数
	index++;//时间戳增加

	num[cur] = index;//记录当前节点的时间戳
	low[cur] = index;//记录当前节点所能回溯的最早时间戳，最开始当然是自己

	for (int i = 1; i <=point; i++)//枚举与当前顶点相邻接的顶点
	{
		if (arr[cur][i]==1)//如果两个顶点相邻接
		{
			if (num[i] == 0)//如果顶点i的时间戳为0，则顶点i还没有被访问过
			{
				child++;//当前顶点的孩子节点数增加
				dfs(flag,num, low, arr, i, cur);//访问顶点i，顶点i的父亲是当前顶点
				low[cur] = min(low[cur], low[i]);//顶点i访问完后，顶点i也有了自己的时间戳，此时更新当前顶点所能回溯的最早时间戳

				//在当前顶点不是根节点的情况下
				if (cur != root && low[i] >= num[cur])//如果存在顶点i最多只能回溯到当前顶点，则说明当前顶点是割点
				{
					flag[cur] = true;
				}
				//在当前顶点是根节点的情况下，如果孩子数超过两个，则是割点
				if (cur == root && child >= 2)
				{
					flag[cur] = true;
				}
			}
			//如果顶点i被访问过，且i不是当前顶点的父亲
			//则i是当前顶点的祖先，更新当前顶点所能回溯的最早时间戳
			else if (i != father)
			{
				low[cur] = min(low[cur], num[i]);
			}
		}
	}

	return;

}

int main()
{
	cin >> point >> edge;

	int** arr = new int*[point + 1];//图数组
	int* num = new int[point + 1];//时间戳数组
	int* low = new int[point + 1];//回溯时间戳数组
	bool* flag = new bool[point + 1];//割点数组
	//初始化邻接矩阵，各个数组
	for (int i = 0; i <= point; i++)
	{
		arr[i] = new int[point + 1];
		for (int j = 0; j <= point; j++)
		{
			arr[i][j] = 0;
		}
		num[i] = 0;
		flag[i] = false;
		low[i] = 0;
	}

	//录入边的信息
	int a, b;
	for (int i = 0; i < edge; i++)
	{
		cin >> a >> b;
		arr[a][b] = 1;
		arr[b][a] = 1;
	}
	//dfs
	dfs(flag,num,low,arr,1, root);
	//输出结果
	for (int i = 1; i <= point; i++)
	{
		if (flag[i] == true)
		{
			cout << i << endl;
		}
	}

	delete[] arr;
	delete[] num;
	delete[] low;
	delete[] flag;
	return 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
void dfs(bool* flag,int* num,int* low,int** arr,int cur, int father)
{
	int child = 0;//记录孩子节点数
	index++;//时间戳增加

	num[cur] = index;//记录当前节点的时间戳
	low[cur] = index;//记录当前节点所能回溯的最早时间戳，最开始当然是自己

	for (int i = 1; i <=point; i++)//枚举与当前顶点相邻接的顶点
	{
		if (arr[cur][i]==1)//如果两个顶点相邻接
		{
			if (num[i] == 0)//如果顶点i的时间戳为0，则顶点i还没有被访问过
			{
				child++;//当前顶点的孩子节点数增加
				dfs(flag,num, low, arr, i, cur);//访问顶点i，顶点i的父亲是当前顶点
				low[cur] = min(low[cur], low[i]);//顶点i访问完后，顶点i也有了自己的时间戳，此时更新当前顶点所能回溯的最早时间戳

				//在当前顶点不是根节点的情况下
				if (cur != root && low[i] >= num[cur])//如果存在顶点i最多只能回溯到当前顶点，则说明当前顶点是割点
				{
					flag[cur] = true;
				}
				//在当前顶点是根节点的情况下，如果孩子数超过两个，则是割点
				if (cur == root && child >= 2)
				{
					flag[cur] = true;
				}
			}
			//如果顶点i被访问过，且i不是当前顶点的父亲
			//则i是当前顶点的祖先，更新当前顶点所能回溯的最早时间戳
			else if (i != father)
			{
				low[cur] = min(low[cur], num[i]);
			}
		}
	}

	return;

}

核心算法思维导图：