无向图的点双连通分量(又称块)

缘起

首先必须说清楚一些基本概念,1 割点（又叫关节点）、割边（又叫关节边或者桥）的意思就是弄掉它就不灵了（即原本的连通图就不连通了）

一个无向连通图存在割边（割点）的充要条件是边连通度=1（点连通度=1）而且割边割点的个数可以不止一个，

点连通度的意思是这个图最少删除掉多少个点可以使得图不再连通.边连通度的意思是这个图最少删掉多少条边可以使得图不再连通.

点（边）连通度>1的图叫做点（边）双连通图（或者叫重连通图），或者简称就是双连通图. 双连通分支（或者叫重连通分支）的概念就很明显了（双连通极大子图嘛），特别地，点双连通分支又叫做块.

本文就是要给出求块的算法. 其实就是在求割点的tarjan算法的过程中顺便干点事情.

分析

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
130
131
132
#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; // 块的数量

	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]) // 注意, 这里的算法虽然基于割点, 但是也没有对根节点做特别处理, 因为就算根节点不是割点(即cur=1&&child=1), 出栈的时候该树边也出栈了, 所以依旧是没有问题的, 重申一下, bcc是包含割点的!
				{
					Edge *tmp = new Edge(cur, *x);
					while(*(s.top())!=*tmp) // 这里不能使用 do...while
					{
						bcc[bccnum].push_back(s.top()); // 弹栈成为bcc(双连通分量)
						s.pop();
					}
					bcc[bccnum].push_back(tmp);
					s.pop();
					bccnum++;
				}
			}
			else if (*x != father && timestamp[*x]<timestamp[cur]) // 限定 timestamp[*x]<timestamp[cur]，是因为 min(low[cur], timestamp[*x]) 在  timestamp[*x]>=timestamp[cur]（注意, 其实不会等于）的情况下没有意义, 因为timestamp[cur]>=low[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();
		}
		puts("");
	}
	return 0;
}
/*
测试数据(结合测试数据理解bcc算法是容易的)
6
1 4
1 3
4 2
3 2
2 5
5 6
6 2
*/

而且本算法就算整个无向连通图不存在割点也是没有问题的, 因为此时 根节点为1并且根节点的child=1, 所以最后弹栈的时候, 边栈中的边就是整个无向连通图