题目链接
AcWing 3719. 畅通工程
题目详情
题目解析
我们来简单看一下题目,我们假设有城镇a与城镇b修路，那么它们就从原来两个独立的个体变成了一个整体的集合,如果我们将个体看做集合的话，就是两个本次独立的集合合并成了一个集合，合并集合,那么这道题的解题方法已经呼之欲出了,就是并查集，然后就是我们如何实现一个并查集了，按照流程来说,一般有三步：
- 初始化集合:首先我们要将所有的个体都先看成一个独立的集合，完成初始化
- 合并集合
- 统计集合
根据上面的三个过程可以得到我们的解题代码：
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1010;
int p[N]; //记录并查集的代表元素int find(int x)
{if (x!=p[x]){p[x] = find(p[x]); //路径压缩}return p[x];
}void merge(int a, int b)
{p[a]=find(a);p[b]=find(b);if (p[a]!=p[b]){p[p[a]] = p[b]; //合并a和b所在的集合}
}int main()
{int n, m;cin>>n>>m;for (int i = 1; i <= n; i++){p[i] = i; //在未实现集合合并之前，每个元素都是自己所在集合的代表元素}int a,b;while(m--){cin>>a>>b;merge(a,b);}int res=0;for(int i=1;i<=n;i++){if(p[i]==i){res++;}}cout<<res-1<<endl;return 0;
}
拓展: 基于go语言实现的解题代码
package mainimport "fmt"const N = 1010var (p = make([]int, N)n, m int
)func find(x int) int{if p[x] != x {p[x] = find(p[x])}return p[x]
}func merge(x, y int) {x = find(x)y = find(y)if x != y {p[x] = y}
}func main() {fmt.Scan(&n, &m)for i :=1;i<=n;i++{p[i]=i}var x, y intfor i := 0; i < m; i++ {fmt.Scan(&x, &y)merge(x, y)}var ans = 0for i := 1; i <= n; i++ {if p[i] == i {ans++}}fmt.Println(ans-1)
}