[并查集 ]
【引入】并查集是啥？
并查集真的是很簡潔而又優雅的資料結構，主要用于解決一些元素分組的問題，它管理一系列不相交的集合，并支持兩種操作：
- 合并（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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/165406.html
標籤：其他
下一篇：找出唯一成對的數（異或運算）