上机算法刷题暑期篇(二) ——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)
}

相关推荐

  1. 记(25)--继续畅通工程

    2024-07-13 07:40:01       52 阅读
  2. dp算法第三(暑期提升)

    2024-07-13 07:40:01       23 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-13 07:40:01       67 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-13 07:40:01       72 阅读
  3. 在Django里面运行非项目文件

    2024-07-13 07:40:01       58 阅读
  4. Python语言-面向对象

    2024-07-13 07:40:01       69 阅读

热门阅读

  1. TypeScript学习笔记

    2024-07-13 07:40:01       26 阅读
  2. MIME 类型

    2024-07-13 07:40:01       24 阅读
  3. 35、php 实现构建乘积数组、正则表达式匹配

    2024-07-13 07:40:01       22 阅读
  4. django ninja get not allowed 能用 put delete

    2024-07-13 07:40:01       22 阅读
  5. 【算法】删除链表的倒数第 N 个结点

    2024-07-13 07:40:01       21 阅读
  6. 力扣-bfs

    2024-07-13 07:40:01       22 阅读
  7. 访问本地SQL Server:巴比达内网穿透的又一妙用

    2024-07-13 07:40:01       23 阅读
  8. 会话固定攻击

    2024-07-13 07:40:01       25 阅读
  9. Json 之 DSL-Json

    2024-07-13 07:40:01       19 阅读