[并查集 ]

【引入】并查集是啥？

并查集真的是很简洁而又优雅的数据结构，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

• 合并（Union）：把两个不相交的集合合并为一个集合。
• 查询（Find）：查询两个元素是否在同一个集合中。

路径压缩可以将树的多层结构简化成1对多

在查询两个元素是否同一组时并不需要一层层上级查找，而是直接找每个人的BOSS

题目链接#

A. 畅通工程

思路：

题目要问最少还需要建设多少条道路？

将城镇群分组，能有路到达的城镇为一组

那么需要再建造的路为城镇组的个数-1

#include<bits/stdc++.h>  //黑夜给了我黑色的双眼
using namespace std;    //而我却用他来寻找光明
const int INF=0x3f3f3f3f;//2020.10.9 23:59
typedef long long ll;
int  pre[1050];
bool t[1050];
int Find(int x) //查询他的BOSS 
{
	int r=x;
	while(r!=pre[r])
		r=pre[r];

	int i=x,j;
	while(pre[i]!=r)
	{
		j=pre[i];
		pre[i]=r;
		i=j;
	}
	return r;
}

void mix(int x,int y) //join in
{
	int fx=Find(x),fy=Find(y);
	if(fx!=fy)
	{
		pre[fy]=fx;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N,M,a,b,i,j,ans;

	while(cin>>N>>M)
	{

		for(i=1; i<=N; i++)        //初始化，每个人的上级都是自己 
			pre[i]=i;

		for(i=1; i<=M; i++)        //将两个城镇联通 
		{
			cin>>a>>b;
			mix(a,b);
		}


		memset(t,0,sizeof(t));
		for(i=1; i<=N; i++)        //标记根结点
		{
			t[Find(i)]=1;
		}
		for(ans=0,i=1; i<=N; i++)
			if(t[i])
				ans++;

		cout<<ans-1<<"\n";
	}


	return 0;
}