畅通工程 HDU 1232——(并查集)

本文主要是介绍畅通工程 HDU 1232——(并查集)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

该题运用并查集算法：https://blog.csdn.net/TSY_1222/article/details/83242115

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1232

C++代码实现：

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e3+6; 
int i, n, m, ans, fa[N];
int find(int x)      //路径压缩 
{return fa[x] == -1 ? x:fa[x]=find(fa[x]);
}
void Merge(int a, int b)   //合并 
{int p1=find(a), p2=find(b);if(p1 != p2)fa[p1] = p2;
}
int main()
{ios::sync_with_stdio(false);     //增加输入输出的效率 cin.tie(0);while(cin>>n>>m, n){
//		if(n==0)
//		break;ans = 0;for(i=1; i<=n; i++)fa[i] = -1;for(i=1; i<=m; i++){int a, b;cin>>a>>b;Merge(a, b);	}	for(i=1; i<=n; i++){if(fa[i] == -1)ans ++;			}cout << ans-1 <<endl;} 	return 0;
}

 

这篇关于畅通工程 HDU 1232——(并查集)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---