自动搬运

查看原文

来自洛谷，原作者为

	Strong_Jelly **

搬运于2025-08-24 21:26:12，当前版本为作者最后更新于2019-02-21 09:18:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目描述

某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府“村村通工程”的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？

这一道题可以用并查集的方法做

思路：输入两个村庄后就把它们连起来，输入完毕后用i从1循环到n，所以如果i的父亲为它本身的话（它是祖先，它没有父亲），ans+1。答案要减1，因为三个点中只需用两条线连接，无需用三条线连接。

并查集

并查集是一种树型的数据结构，用于处理一些不交集的合并及查询问题（不交集的意思是两个集合中没有相同的元素）。

并查集分两个主要步骤——合并，查找

1.find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。

code :

int find(int x) 
{
    if(x != fa[x])//当x不等于它的爸爸时(当它是祖先时，它没有爸爸) 
    {
        fa[x] = find(fa[x]);//继续找他的爸爸的爸爸 
    }
    return fa[x];//返回祖先 
}//查找 

2.unity：将两个子集合并成同一个集合。

code :

void unity(int x, int y)
{
    int r1 = find(x);//找到x的祖先 
    int r2 = find(y);//找到y的祖先 
    fa[r1] = r2;//祖先和祖先结为父子(谁是父亲谁是儿子都可以) 
}//合并 

完整代码如下：

#include <bits/stdc++.h>
using namespace std;
int fa[1000001], n, m, x, y;
int find(int x)//并查集(路径压缩) 
{
    if(x != fa[x])//当x不等于它的爸爸时(当它是祖先时，它没有爸爸) 
    {
        fa[x] = find(fa[x]);//继续找他的爸爸的爸爸 
    }
    return fa[x];//返回祖先 
}//查找 
void unity(int x, int y)
{
    int r1 = find(x);//找到x的祖先 
    int r2 = find(y);//找到y的祖先 
    fa[r1] = r2;//祖先和祖先结为父子(谁是父亲谁是儿子都可以) 
}//合并 
int main()
{
	while(true)
	{
		int ans = 0;//ans要在循环中定义为0
		scanf("%d", &n);
		if(n == 0)
		{
			return 0;
		}
		scanf("%d", &m);
	    for(int i = 1; i <= n; i++)
	    {
	        fa[i] = i;//初始化自己的父亲是自己 
	    }
	    for(int i = 1; i <= m; i++)
	    {
	        scanf("%d %d", &x, &y);
	        unity(x, y);//合并x和y 
	    }
	    for(int i = 1; i <= n; i++)
	    {
	    	if(find(i) == i)//自己的父亲等于自己本身
	    	{
	    		ans++;
			}
		}
		printf("%d\n", ans - 1);//答案减一 
	}
    return 0;
}