并查集的使用

Myth丶恋晨 2022-05-26 04:09 95阅读 0赞

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

算法实现，包括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  
应该输出：

#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++