c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之并查集總結(jié)

發(fā)布時(shí)間：2020-10-03 03:02:09 來源：腳本之家閱讀：295 作者：Alger_jhun 欄目：編程語(yǔ)言

并查集(Union-Find Set)：

一種用于管理分組的數(shù)據(jù)結(jié)構(gòu)。它具備兩個(gè)操作：(1)查詢?cè)豠和元素b是否為同一組 (2) 將元素a和b合并為同一組。

注意：并查集不能將在同一組的元素拆分為兩組。

并查集的實(shí)現(xiàn)：

用樹來實(shí)現(xiàn)。

c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之并查集總結(jié)

使用樹形結(jié)構(gòu)來表示以后，每一組都對(duì)應(yīng)一棵樹，然而我們就可以將這個(gè)問題轉(zhuǎn)化為樹的問題了，我們看兩個(gè)元素是否為一組我們只要看這兩個(gè)元素的根是否一致。顯然，使用樹形結(jié)構(gòu)將問題簡(jiǎn)單化了。合并時(shí)是我們只需要將一組的根與另一組的根相連即可。

并查集的核心在于，一棵樹的所有節(jié)點(diǎn)根節(jié)點(diǎn)都為一個(gè)節(jié)點(diǎn)。使用Find函數(shù)查詢時(shí)，也是查詢到這個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)。

一行并查集：

int find(int x)
{
 return p[x]==x? x:find(p[x]); //x的父節(jié)點(diǎn)保存在p[x]中，如果沒有父節(jié)點(diǎn)則p[x]=x。
}

實(shí)現(xiàn)：

int node[i]; //每個(gè)節(jié)點(diǎn) 
 
//初始化n個(gè)節(jié)點(diǎn) 
void Init(int n){ 
 for(int i = 0; i < n; i++){ 
 node[i] = i; 
 } 
} 
//查找當(dāng)前元素所在樹的根節(jié)點(diǎn)(代表元素) 
int find(int x){ 
 if(x == node[x]) 
 return x; 
 return find(node[x]); 
} 
//合并元素x， y所處的集合 
void Unite(int x, int y){ 
 //查找到x，y的根節(jié)點(diǎn) 
 x = find(x); 
 y = find(y); 
 if(x == y) 
 return ; 
 //將x的根節(jié)點(diǎn)與y的根節(jié)點(diǎn)相連 
 node[x] = y; 
} 
//判斷x，y是屬于同一個(gè)集合 
bool same(int x, int y){ 
 return find(x) == find(y)

并查集的路徑壓縮：

在特殊情況下，這棵樹是一條長(zhǎng)長(zhǎng)的樹鏈，設(shè)鏈的最后一個(gè)結(jié)點(diǎn)為x，則每次執(zhí)行find(x)都會(huì)遍歷整條鏈。效率十分的地下。改進(jìn)方法很簡(jiǎn)單，只要把遍歷過的結(jié)點(diǎn)都改成根的子結(jié)點(diǎn)，后面的查詢就會(huì)變的快很多。

c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之并查集總結(jié)

并查集的復(fù)雜度

加入這兩個(gè)優(yōu)化之后，并查集的效率就非常高。對(duì)n個(gè)元素的并查集操作一次的復(fù)雜度是： O(α(n))。這里，α(n)是阿克曼(Ackermann)函數(shù)的反函數(shù)。效率要高于O(log n)。

不過這里O(α(n))是平均復(fù)雜度。也就是說，多次操作之后平均復(fù)雜度為O(α(n))，換而言之，并不是每一次操作都滿足O(α(n))。

路徑壓縮后的優(yōu)化代碼：

 int node[i]; //每個(gè)節(jié)點(diǎn) 
 int rank[i]; //樹的高度 
 
 //初始化n個(gè)節(jié)點(diǎn) 
 void Init(int n){ 
 for(int i = 0; i < n; i++){ 
  node[i] = i; 
  rank[i] = 0; 
 } 
 } 
 //查找當(dāng)前元素所在樹的根節(jié)點(diǎn)(代表元素) 
 int find(int x){ 
 if(x == node[x]) 
  return x; 
 return node[x] = find(node[x]); //在第一次查找時(shí)，將節(jié)點(diǎn)直連到根節(jié)點(diǎn) 
 } 
 //合并元素x， y所處的集合 
 void Unite(int x, int y){ 
 //查找到x，y的根節(jié)點(diǎn) 
 x = find(x); 
 y = find(y); 
 if(x == y) 
  return ; 
 //判斷兩棵樹的高度，然后在決定誰(shuí)為子樹 
 if(rank[x] < rank[y]){ 
  node[x] = y; 
 }else{ 
  node[y] = x; 
  if(rank[x] == rank[y]) rank[x]++: 
 } 
 } 
 //判斷x，y是屬于同一個(gè)集合 
 bool same(int x, int y){ 
 return find(x) == find(y); 
 }

實(shí)例分析：

題目：部落

在一個(gè)社區(qū)里，每個(gè)人都有自己的小圈子，還可能同時(shí)屬于很多不同的朋友圈。我們認(rèn)為朋友的朋友都算在一個(gè)部落里，于是要請(qǐng)你統(tǒng)計(jì)一下，在一個(gè)給定社區(qū)中，到底有多少個(gè)互不相交的部落？并且檢查任意兩個(gè)人是否屬于同一個(gè)部落。

輸入格式：

輸入在第一行給出一個(gè)正整數(shù)N（<= 104），是已知小圈子的個(gè)數(shù)。隨后N行，每行按下列格式給出一個(gè)小圈子里的人：

K P[1] P[2] ... P[K]

其中K是小圈子里的人數(shù)，P[i]（i=1, .., K）是小圈子里每個(gè)人的編號(hào)。這里所有人的編號(hào)從1開始連續(xù)編號(hào)，最大編號(hào)不會(huì)超過104。

之后一行給出一個(gè)非負(fù)整數(shù)Q（<= 104），是查詢次數(shù)。隨后Q行，每行給出一對(duì)被查詢的人的編號(hào)。

輸出格式：

首先在一行中輸出這個(gè)社區(qū)的總?cè)藬?shù)、以及互不相交的部落的個(gè)數(shù)。隨后對(duì)每一次查詢，如果他們屬于同一個(gè)部落，則在一行中輸出“Y”，否則輸出“N”。

輸入樣例：
4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7

輸出樣例：

10 2
Y
N

分析：典型并查集問題。

一個(gè)部落對(duì)應(yīng)一個(gè)集合。根節(jié)點(diǎn)數(shù)量等于部落數(shù)量。
并查集把每個(gè)部落的人連起來，記錄哪些人出現(xiàn)過，枚舉標(biāo)號(hào)10000，找出有多少人和部落，查詢并查集維護(hù)。

源碼分析：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int pre[10005];
int f[10005];
 
void init() { //初始化父集合pre[10005]，以及出現(xiàn)的標(biāo)志數(shù)組f[10005]
	for(int i=0; i<10004; i++)
		pre[i]=i, f[i]=0;
}
 
int find(int x) { //并查集查找根節(jié)點(diǎn)的 遞歸程序
	return pre[x]==x? x : pre[x]=find(pre[x]);
}
 
int main()
{
	init();
	int n,q,k,a,b;
	cin>>n;
	for(int i=0; i<n; i++) {
		cin>>k>>a;
		f[a]=1;
		for(int j=1; j<k; j++) {
			cin>>b;
			f[b]=1;
			int x=find(a);
			int y=find(b);
			if(x!=y) pre[x]=y;
		}
	}
	int cnt=0,tot=0; //cnt為所有人數(shù) tot為部落數(shù)量
	for(int i=0; i<10004; i++) {
		if(f[i] == 1) { //如果標(biāo)志為1 則說明出現(xiàn)過，cnt加一
			cnt++;
			if(pre[i]==i) tot++; //如果下標(biāo)為本身 說明其為根節(jié)點(diǎn) 根節(jié)點(diǎn)數(shù)量為部落的數(shù)量
		}
	}
	cout<<cnt<<" "<<tot<<endl;
	cin>>q;
	for(int i=0; i<q; i++) {
		cin>>a>>b;
		if(find(a) == find(b)) //若兩參數(shù) 有同一根節(jié)點(diǎn) 說明為一個(gè)部落。
			cout<<"Y"<<endl;
		else cout<<"N"<<endl;
	}
	return 0;
}

好了，這篇文章就介紹到這了。

向AI問一下細(xì)節(jié)

c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之并查集 總結(jié)

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽

c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之并查集總結(jié)