博客

并查集实际上是数据结构中树的应用，每个子树最终连接到一个根节点上

算法实现，包括find()函数–找到子树的根节点，和join（）函数–合并子树

find()算法实现:

int find(int x) 
{
	int r=x;
	while(r!=pre[r]) 
	{
		r = pre[r];
	}
	int i = x,j = r;
	while(i != r) //路径压缩算法
	{
		j = pre[i];//改变前导节点前记录值
		pre[i] = r;//前导节点改为根节点
		i = j;
	}
	return r;
}

join()算法实现：

void join(int x,int y) 
{
	int fx = find(x);
	int fy = find(y);
	if(fx!=fy) 
	{
		pre[fx] = fy;
	}
}

题目引入：

第八届蓝桥杯：风险度量

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

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
int pre[1005],route[1005][2];
int sum = 0;

int find(int x) 
{
	int r=x;
	while(r!=pre[r]) 
	{
		r = pre[r];
	}
	int i = x,j = r;
	while(i != r) //路径压缩算法
	{
		j = pre[i];//改变前导节点前存储值
		pre[i] = r;
		i = j;//改变前导节点的值
	}
	return r;
}

void join(int x,int y) 
{
	int fx = find(x);
	int fy = find(y);
	if(fx!=fy) 
	{
		pre[fx] = fy;
	}
}

int main() {
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i = 0; i<m; i++) 
	{
		scanf("%d %d",&route[i][0],&route[i][1]);
	}

	int p1,p2;
	scanf("%d %d",&p1,&p2);
	
	
	for(int i = 0; i<n; i++) pre[i] = i;
	for(int i = 0; i<m; i++) 
	{
		join(route[i][0],route[i][1]);
	}
	int a = find(p1);
	int b = find(p2);
	if(a!=b) 
	{
		printf("-1\n");
	} 
	else 
	{
		for(int i = 1; i<=n; i++) 
		{
			if(p1 == i||p2 == i) 
			{
				continue;
			}
			for (int j = 1; j <= n; j++)pre[j] = j;
			for(int j = 0; j < m; j++) 
			{
				if(route[j][0] == i||route[j][1] == i) 
				{
					continue;
				}
				int a = find(route[j][0]);
				int b = find(route[j][1]);
				if(a>b) {
					a^=b;
					b^=a;
					a^=b;
				} 
				if(a!=b) 
				{
					pre[b] = a;
				}
			}
			a = find(p1);
			b = find(p2);
			if(a!=b) sum++;
		}
		printf("%d\n",sum);
	}
	return 0;
}

1、判定是否两个通信节点是否联通

2、连通的前提下遍历所有节点，去掉该节点与u、v连接的边，如果u、v依然连通，说明该节点不是关键点，否则是关键点sum++