上机算法刷题暑期篇(二) ——AcWing 3719. 畅通工程(天大)

题目链接

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 main

import "fmt"

const N = 1010

var (
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 int
for i := 0; i < m; i++ {
fmt.Scan(&x, &y)
merge(x, y)
}
var ans = 0
for i := 1; i <= n; i++ {
if p[i] == i {
ans++
}
}
fmt.Println(ans-1)
}

原文地址：https://blog.csdn.net/qq_73924465/article/details/140387811

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！