无向连通图的割点

缘起

所谓无向连通图的关节点的意思是，删掉该节点之后, 无向连通图变得不连通了. 这就是关节点, 即割点. 较之其它顶点， 关节点更为重要。 在网络系统中它们对应于网关， 决定子网之间能否连通。 在航空系统中， 某些机场的损坏，将同时切断其它机场之间的交通。 故在资源总量有限的前提下， 找出关节点并重点予以保障， 是提高系统整体稳定性和鲁棒性的基本策略。

分析

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
#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
{
	int n;
	vector<int> vertex[MAX_NUM];
	
	int index; // 时间
	int timestamp[MAX_NUM]; // 时间戳
	int low[MAX_NUM];  // low 的意思与scc的tarjan算法的low不一样，这里的low是不经过父节点能够回到的最早时间戳
	bool flag[MAX_NUM]; // 是否是割点

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

	void cut(int cur, int father) // 求割点 由tarjan发明, cur是当前节点, father是其深搜树的父节点
	{
		timestamp[cur] = low[cur] = ++index;
		int child = 0; // cur的直接儿子的个数
		for (it x = vertex[cur].begin(); x!=vertex[cur].end();x++)
		{
			if (!timestamp[*x])
			{
				child++;
				cut(*x, cur);
				low[cur] = min(low[cur], low[*x]);
				if (cur!=1&&low[*x]>=timestamp[cur]) // 如果有一个直接儿子(*x)不能回到父亲(cur)之前, 则cur就是割点, 这里1是根节点, 这个规律对于根节点不适用. 原因很显然, timestamp[1]=1已经是最小了. 那岂不是根节点一定时割点? 不对吧?
				{
					flag[cur] = true;
				}
				else if(cur == 1 && child >1)
				{
					flag[1] = true; // 根节点判定是否是割点，要使用孩子个数
				}
			}
			else if (*x != father) // 如果是返祖边
			{
				low[cur] = min(low[cur], timestamp[*x]); // 注意, 为什么这里只能使用timestamp[*x]而上面却可以使用low[*x]? 因为*x 可能就是割点, 譬如本例子中的2是6的祖先, 如果使用low[2]来min的话,则*x就可以到1去了. 这显然是不对的. 但是上面使用low可以, 因为上面是cur->*x,没有走father. 有人可能会问, 既然low是不通过父节点能回到最早的时刻, 那cur->*x就不会经过cur的father了吗? 不会的, 因为这样的话, 一定存在一条返祖变 son->father, 其中son是father1的孩子（注意，无向图哦）.一旦这样，son能回去的low就是用timestamp[father]来min的, 所以使用low[*x]也是可以的,整个过程见下图.好事儿的读者又要问了: 为什么scc的tarjan算法没有这么多屁事儿?(都是使用low来min) 因为scc-tarjan算法没有求割点, 正因为是求割点，所以x!=father的时候要谨慎.这里才是不经过父节点的真正体现
			}
		}
	}

	
};

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	Graph g;
	g.cut(1,1);
	for (int i = 1; i<= g.n; i++)
	{
		if (g.flag[i])
		{
			cout << i;
		}
	}
	puts("");
	return 0;
}
/*
测试数据
6
1 3
1 4
2 4
2 3
5 6
2 6
2 5
*/