无向连通图的割边(又称桥)

缘起

类比于无向连通图的割点, 无向连通图的割边的定义就是去掉之后, 图变的不再连通. 就好像是城市的交通要道一样.

分析

与割边的算法相比, 割点唯一的不同就是改了一个符号

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
#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];

	Graph()
	{
		index = 0;
		memset(timestamp,0,sizeof(timestamp));
		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) // 求割边
	{
		timestamp[cur] = low[cur] = ++index;
		for (it x = vertex[cur].begin(); x!=vertex[cur].end();x++)
		{
			if (!timestamp[*x])
			{
				cut(*x, cur);
				low[cur] = min(low[cur], low[*x]);
				if (low[*x]>timestamp[cur]) // 割边和割点唯一的不同就在于这里, >=改成了 >, 即严格回不到父节点,而且去掉了对根节点的判断.因为割边对于根节点的处理和其他顶点是一致的
				{
					cout << *x << "---" << cur << endl;
				}
			}
			else if (*x != father)
			{
				low[cur] = min(low[cur], timestamp[*x]); 
			}
		}
	}

	
};

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	Graph g;
	g.cut(1,1);
	return 0;
}
/*
测试数据
6
1 4
1 3
4 2
3 2
2 5
5 6
*/

注意，上面的程序已经没有了child以及根节点的判断, 这是因为这里求的是割边，而不是割点, 判断出根节点并不能确定割边.