无向连通图的边双连通分量

缘起

【1】和【2】中我们分别引入了无向连通图的割点和割边（即桥）的概念. 继而【3】中引入了块（即点bcc）的概念，并给出了相应的算法. 这里将给出边bcc的算法.

分析

正如块算法是在求割点的时候干点事情（边的入栈和出栈）一样, 边bcc算法其实就是在求割边的时候顺便做点事情. 注意，与求块不同, 那里涉及割点的边还是要入栈的. 但是这里涉及割点的边是不需要入栈的

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#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;

struct Edge
{
	int x,y;

	Edge(int x, int y):x(x),y(y){}

	bool operator ==(Edge e) //重载边的相等运算符, 即重新定义什么叫做边相等
	{
		return e.x ==this->x &&e.y==this->y || e.x==this->y&&e.y ==this->x;
	}

	bool operator !=(Edge e)
	{
		return !(*this==e);
	}

	void print()
	{
		printf("(%d, %d)", x,y);
	}
};

typedef vector<Edge*>::iterator ite;

typedef vector<int>::iterator it;

struct Graph
{
	int n;
	vector<int> vertex[MAX_NUM]; // 邻接链表法表示图

	int index; 
	int timestamp[MAX_NUM]; 
	int low[MAX_NUM]; // 不通过它的父亲能回到的最早时刻



	stack<Edge*> s;

	int bccnum; // 边bcc的数量

	vector<Edge*> bcc[MAX_NUM*(MAX_NUM-1)>>1]; // 边双连通分量

	Graph()
	{
		index = bccnum =  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 getbcc(int cur, int father)
	{
		timestamp[cur] = low[cur] = ++index;
		for (it x = vertex[cur].begin(); x!=vertex[cur].end();x++)
		{
			if (!timestamp[*x])
			{
				s.push(new Edge(cur,*x));
				getbcc(*x, cur);
				low[cur] = min(low[cur], low[*x]);
				if (low[*x]>timestamp[cur]) // 这是与块算法第一处不同, 毕竟块算法基于割点, 而边bcc算法基于桥（割边）
				{
					Edge *tmp = new Edge(cur, *x);
					while(*(s.top())!=*tmp)
					{
						bcc[bccnum].push_back(s.top());
						s.pop();
					}
					s.pop(); // 割边(cur,*x)只是单纯的出栈,这是和块算法第二处不同
					bccnum++;
				}
			}
			else if (*x != father && timestamp[*x]<timestamp[cur]) 
			{
				low[cur] = min(low[cur], timestamp[*x]); 
				s.push(new Edge(cur, *x)); 
			}
		}
	}


};

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	Graph g;
	g.getbcc(1,1);
	printf("一共%d个边双连通分量\n", g.bccnum);
	for (int i = 0; i<g.bccnum; i++)
	{
		for (ite x = g.bcc[i].begin(); x!=g.bcc[i].end(); x++)
		{
			(*x)->print();
		}
	}
	return 0;
}
/*
测试数据
6
1 4
1 3
4 2
3 2
2 5
5 6
*/

其实上面的程序是有问题的, 因为2-5和5-6都是割边. 但是出栈之后, 就都没有了. 即bcc[0]和bcc[1]都是空的边栈. 所以 g.s 中剩下的边就构成一个bcc. 所以就输出结果而言，是不完美的.

参考

【1】https://yfsyfs.github.io/2019/05/24/%E6%97%A0%E5%90%91%E8%BF%9E%E9%80%9A%E5%9B%BE%E7%9A%84%E5%89%B2%E7%82%B9/

【2】https://yfsyfs.github.io/2019/05/24/%E6%97%A0%E5%90%91%E8%BF%9E%E9%80%9A%E5%9B%BE%E7%9A%84%E5%89%B2%E8%BE%B9-%E5%8F%88%E7%A7%B0%E6%A1%A5/

【3】https://yfsyfs.github.io/2019/05/24/%E6%97%A0%E5%90%91%E5%9B%BE%E7%9A%84%E7%82%B9%E5%8F%8C%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F-%E5%8F%88%E7%A7%B0%E5%9D%97/