Zhao70's Blog

图上的关键点-并查集

发表于 | 分类于

题目

标题：风险度量

X星系的的防卫体系包含 n 个空间站。这 n 个空间站间有 m 条通信链路，构成通信网。
两个空间站间可能直接通信，也可能通过其它空间站中转。

对于两个站点x和y (x != y), 如果能找到一个站点z，使得：
当z被破坏后，x和y无法通信，则称z为关于x,y的关键站点。

显然，对于给定的两个站点，关于它们的关键点的个数越多，通信风险越大。

你的任务是：已知网络结构，求两站点之间的通信风险度，即：它们之间的关键点的个数。

输入数据第一行包含2个整数n(2 <= n <= 1000), m(0 <= m <= 2000),分别代表站点数，链路数。
空间站的编号从1到n。通信链路用其两端的站点编号表示。
接下来m行，每行两个整数 u,v (1 <= u, v <= n; u != v)代表一条链路。
最后1行，两个数u,v，代表被询问通信风险度的两个站点。

输出：一个整数，如果询问的两点不连通则输出-1.

例如：
用户输入：
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6
则程序应该输出：
2

思路解析

  1. 最开始检查a, b两点是否联通，否则，输出 -1 程序结束
  2. 从1开始去除每一个点后，使用并查集检查是否在同一个集合中

代码

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
#include <iostream>
using namespace std;
int nVer, nEdge;
int edge[2500][2];
int arr[1500];
bool merge(int, int);
int getFather(int);
int main(int argc, char const *argv[])
{
	cin >> nVer >> nEdge;
	for(int i = 0; i < nEdge; i++)
	{
		cin >> edge[i][0] >> edge[i][1];
	}
	int start, end;
	cin >> start >> end;
    for(int j = 1; j <= nVer; j++)
    {
        arr[j] = j;
    }
    for(int j = 0; j < nEdge; j++)
    {
        merge(edge[j][0], edge[j][1]);
    }
	if(merge(start, end) == false)
	{
        cout << "-1" << endl;
        return 0;
	}
	int cnt = 0;
	//遍历每个去掉的点
	for(int i = 1; i <= nVer; i++)
	{
		//去除需要检查联通的两点，这两点不需要遍历
	    if(i == start || i == end)
            continue;
		for(int j = 1; j <= nVer; j++)
		{
			arr[j] = j;
		}
		//合并已知点
		for(int j = 0; j < nEdge; j++)
		{
			//已经去除的点不需要继续合并
			if(edge[j][0] == i || edge[j][1] == i)
				continue;
			merge(edge[j][0], edge[j][1]);
		}
		if(merge(start, end) == false)
		{
			cnt++;
		}
	}
		cout << cnt << endl;
	return 0;
}
int getFather(int node)
{
	if(arr[node] == node)
		return node;
	node = getFather(arr[node]);
	return node;
}
bool merge(int t1, int t2)
{
	t1 = getFather(t1);
	t2 = getFather(t2);
	if(t1 == t2)
	{
		return true;
	}
	if(t1 < t2)
		arr[t2] = t1;
	else
		arr[t1] = t2;
	return false;
}