畅通工程

畅通工程
题面


题意找出最少要加几条路才可以让所有城市之间连通
分析
这是一道有关并查集的题目，就是确定连通分量的个数
以下是并查集的原理

以上图为例，h是b的父亲节点，c是b的根节点。如果两个节点之间有联系，那么其中一个点就是另一个点的父亲节点。以此类推，最高层即没有父亲节点的点成为根节点。
如何判断b与g之间是有联系（b与g的根节点如果有联系就代表这两个点有联系）
b->h->c
g->d->f
如果c与f是有联系的，那么这两颗树就是有联系的，也就是说这两颗树可以合并成一棵树，那么b与g是有联系的。
概念上可以很简单地理解，但是代码稍微难理解一点。
代码：

int Find(int x)
{
	while(father[x]!=x)
		x=father[x];
	return x;//返回最初x根节点的位置，所以使用while循环直到根节点（根节点的father[x]=x）
}
//合并函数
void combine(int a,int b)
{
    int temp_a,temp_b;
	temp_a=Find(a);
	temp_b=Find(b);
	if(temp_a!=temp_b)
		father[temp_a]=temp_b;//写成father[temp_b]=temp_a也是可以的
	return ;
}
//确定连通分量个数

当我们掌控这两个函数的时候就可以用并查集来求解连通分量的个数
直接用循环查找father[i]与i是否相等来更新连通分量的个数。
而本道题的答案就是连通分量的个数-1

AC代码

/* 找到连通块的个数 连通块个数-1就是ans */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int n,m,father[1005],a,b,cnt=0,ra,rb;
int Find (int t){
while(father[t]!=t) t=father[t];
return t;
}
int main(){
while(scanf("%d",&n),n){
cnt=0;
scanf("%d",&m);
for(int i=1;i<=n;i++)
father[i]=i;
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
ra=Find(a);
rb=Find(b);
if(ra!=rb) father[ra]=rb;
}
for(int i=1;i<=n;i++)
if(father[i]==i) cnt++;
cout<<cnt-1<<endl;
}
return 0;
}

//Itree98大佬提供
#include <stdio.h>
const int MAX=1000;
int father[MAX];
 
//初始化函数
void Init(int n)
{
    int i;
	for(i=1;i<=n;i++)
		father[i]=i;
}
//查找函数
int Find(int x)
{
	while(father[x]!=x)
		x=father[x];
 
	return x;
}
//合并函数
void combine(int a,int b)
{
    int temp_a,temp_b;
	temp_a=Find(a);
	temp_b=Find(b);
 
	if(temp_a!=temp_b)
		father[temp_a]=temp_b;
}
//确定连通分量个数
int find_ans(int n)
{
    int i,sum=0;
    for(i=1;i<=n;++i)
        if(father[i]==i)
            ++sum;
    return sum;
}
 
int main()
{
	int i,n,m,a,b;
 
	while(scanf("%d",&n)!=EOF)
	{
	    if(!n)  break;
		Init(n);
		scanf("%d",&m);
 
		for(i=0;i<m;++i)
		{
			scanf("%d%d",&a,&b);
			combine(a,b);
		}
		printf("%d\n",find_ans(n)-1);
	}
	return 0;
}
 

总结
以后遇到图论中求连通分量的个数的时候使用并查集就可以解决
其实第一个AC代码耗时只有15ms,而大佬提供的有31s，所以为了代码运行速度更快，
可以尝试把有些简单的函数放在主函数里面。