一、什么是并查集
在計算機科學中，并查集是一種樹型的資料結構，用于處理一些不交集的合并及查詢問題，有一個聯合-查找演算法（union-find algorithm）定義了兩個用于次資料結構的操作：
- Find：確定元素屬于哪一個子集，它可以被用來確定兩個元素是否屬于同一子集，
- Union：將兩個子集合并成一個集合，
二、主要操作
- 初始化：把每個點所在的集合初始化為其自身，
for(int i=1;i<=n;i++)
f[i]=i;
- 查找：查找元素所在的集合，即根節點，
int find(int x)
{
while(f[x]!=x)
x=f[x];
return x;
}
- 合并：將兩個元素所在的集合合并為一個集合，
void Union(int x1,int x2)
{
int t1=find(x1);
int t2=find(x2);
if(t1!=t2)
f[t2]=t1;
}
三、優化
上面的代碼看似簡潔，但是每一次find操作的時間復雜度為O(H)，H為樹的高度，由于我們沒有對樹做特殊處理，所以樹的不斷合并可能會使樹嚴重不平衡，最壞情況每個節點都只有一個子節點，
所以在find函式里采用路徑壓縮，
int find(int x) //查找x元素所在的集合,回溯時壓縮路徑
{
if (x != f[x])
{
f[x] = find(f[x]);
//從x結點搜索到祖先結點所經過的結點都指向該祖先結點
}
return f[x];
}
四、模板題
洛谷P3367【模板】并查集
#include<bits/stdc++.h>
using namespace std;
int n,m;
int f[10002];
int find(int x)
{
if(x!=f[x])
f[x]=find(f[x]);
return f[x];
}
void Union(int x1,int x2)
{
int t1=find(x1);
int t2=find(x2);
if(t1!=t2) //祖先不一樣
f[t2]=t1; //把t2的祖先變為x1的祖先t1
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=0;i<m;i++)
{
int z,x,y;
cin>>z>>x>>y;
if(z==1)
Union(x,y);
else
{
if(find(x)!=find(y))cout<<"N"<<endl;
else cout<<"Y"<<endl;
}
}
return 0;
}
五、最小生成樹
一個有n個結點的連通圖的生成樹是原圖的極小聯通子圖，期包含原圖的所有n個結點，且有保持圖連通的最少邊，
最小生成樹其實就是最小權重生成樹的簡稱，
Kruskal演算法
- 將圖的所有邊按照權值從小到大排序
- 遍歷所有排好序的邊，若構不成回路，則將該邊加入到集合中
- 直到找出n-1條邊
例題：繁忙的都市
#include<bits/stdc++.h>
using namespace std;
int n,m;
int s,maxm;
int p[100002];
struct node{
int u;
int v;
int c;
}info[100002];
bool cmp(node x1,node x2)
{
if(x1.c!=x2.c)return x1.c<x2.c;
else if(x1.u!=x2.u) return x1.u<x2.u;
else return x1.v<x2.v;
}
int find(int x) //查找x元素所在的集合,回溯時壓縮路徑
{
if (x!=p[x])
{
p[x]=find(p[x]);
}
return p[x];
}
void bcj(int x1,int x2)//把x2并入x1的集合
{
int t1,t2;//存盤祖先節點
t1=find(x1);
t2=find(x2);
if(t1!=t2)p[t2]=t1;
}
int main()
{
cin>>n>>m;//n就是頂點數，m是邊數
for(int i=1;i<=n;i++)
{
p[i]=i;
}
for(int i=0;i<m;i++)
{
cin>>info[i].u>>info[i].v>>info[i].c;
}
sort(info,info+m,cmp);
for(int i=0;i<m;i++)//遍歷所有的邊
{
if(find(info[i].u)!=find(info[i].v))
{
bcj(info[i].u,info[i].v);//把v并入u的集合
maxm=max(maxm,info[i].c);
}
}
cout<<n-1<<" "<<maxm;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/135944.html
標籤：其他