一、并查集定義

并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不想交集合的合并與查找問題。換言之，disjointSet主要包括unionSet（合并集合）與findRoot（查找集合）兩種操作，程序?qū)崿F(xiàn)上有quick-find和quick-union兩種性能傾向。

二、并查集的用途

并查集主要應(yīng)用在無向圖的動(dòng)態(tài)聯(lián)通性上。例如網(wǎng)絡(luò)連接判斷，在pat中經(jīng)常用于解決的一類題目是“城市聯(lián)通的問題”，本題后面會(huì)以top1001的“Battle over cities--hard version"為例，在編程中使用并查集算法。

變量名等同性問題，在程序中，可以聲明多個(gè)引用來指向同一對象，這個(gè)時(shí)候就可以通過為程序中聲明的引用和實(shí)際對象建立動(dòng)態(tài)連通圖來判斷哪些引用實(shí)際上是指向同一對象。

三、并查集的程序?qū)崿F(xiàn)

并查集有單鏈表實(shí)現(xiàn)，也有用有根樹來實(shí)現(xiàn)（雙親表示法）。

本文主要介紹后一種，這種方法更為快速，通用，易懂，一棵樹代表一個(gè)集合，樹的根結(jié)點(diǎn)的序號(hào)代表這個(gè)集合的編號(hào)。

在細(xì)分，有數(shù)組表示法。

vector<int> parents,ranks,dates;

類表示法

class disjointSet{

     vector<int> parents,ranks,dates;

     int cnt;

};

數(shù)組表示法最為靈活，適合小型題目。類表示法適合大型工程，更符合面向?qū)ο蟮穆纷樱拙S護(hù)，易擴(kuò)展。

四、battle over cities---hardversion

題目中給出若干城市和某些道路，道路有好有壞。戰(zhàn)爭中，最重要的就是要確保城市之間的連通性。如果某個(gè)城市陷落，要重建連通性花費(fèi)的代價(jià)越高，這個(gè)城市就越重要。

1，先用valid的路（出去包含淪陷的那城市的道路）將城市聯(lián)通。

2，然后將invalid路按cost排序。

3，最后選擇invalid邊，將城市聯(lián)通起來，直到只剩一個(gè)集合為止。

有點(diǎn)像變形的kruskal算法。

這里有兩個(gè)特例，重建連通性的costAll為0，還有個(gè)是無法重建連通性，程序中用costAll=INT_MAX來表達(dá)。

1.使用并查集的數(shù)組表示法，屬于quick-union的類型

添加了ranks的優(yōu)化手段，來平衡一下樹的高度路徑壓縮那種優(yōu)化手段一直都有，是在findRoot遞歸函數(shù)里使用的。

添加了dates來記錄數(shù)據(jù)，這個(gè)例子里面表達(dá)集合里元素的數(shù)目。不過dates在本題里面沒有用。

本題里的并查集編碼，采用的是“數(shù)組表示法”Union，findRoot是明擺地寫出來的，其他的并查集api也容易實(shí)現(xiàn)。

添加了ranks的優(yōu)化手段，來平衡一下樹的高度路徑壓縮那種優(yōu)化手段一直都有，是在findRoot遞歸函數(shù)里使用的。添加了dates來記錄數(shù)據(jù)，這個(gè)例子里面表達(dá)集合里元素的數(shù)目。不過dates在本題里面沒有用。本題里的并查集編碼，采用的是“數(shù)組表示法”Union，findRoot是明擺地寫出來的，其他的并查集api也容易實(shí)現(xiàn)。#include<stdio.h>#include<vector>using std::vector;#include<algorithm>using std::sort;#include<limits.h>struct edge {	int a, b;	int cost;	edge(int a_ = -1, int b_ = -1, int cost_ = -1) :a(a_), b(b_), cost(cost_) {}	bool Operator<(const struct edge &x) const {		return cost < x.cost;	}//operator<};int findRoot(vector<int> &parents, int x) {	if (parents[x] == x)return  x;	return parents[x] = findRoot(parents, parents[x]);}//findRootvoid Union(int rootA,int rootB,vector<int> &ranks,vector<int> &parents,vector<int> &dates,int &cnt) {	if (rootA == rootB)return;	if (ranks[rootA] == ranks[rootB])++ranks[rootB];	if (ranks[rootA] < ranks[rootB])parents[rootA] = rootB, dates[rootB] += dates[rootA];	else parents[rootB] = rootA, dates[rootA] += dates[rootB];	++cnt;	return;}//Unionint main() {	freopen("in.txt", "r", stdin);	int N(-1), M(-1);	scanf("%d%d", &N, &M);	vector<edge> edges_valid, edges_invalid;	int validEdgeCnt(0);	for (int i(0); i < M; ++i) {		int a(-1), b(-1), cost(-1), valid(-1);		scanf("%d%d%d%d", &a, &b, &cost, &valid);		if (valid == 1)edges_valid.push_back(edge(a, b, cost)), ++validEdgeCnt;		else edges_invalid.push_back(edge(a, b, cost));	}//for i	sort(edges_invalid.begin(), edges_invalid.end());	vector<int> outputs;	int maxCost(0);	for (int i(1); i <= N; ++i) {		int cnt(0);		vector<int> parents(N + 1, -1);		for (int j(0); j < N + 1; ++j)parents[j] = j;		vector<int> ranks(N + 1, 0);		vector<int> dates(N + 1, 1);		for (int j(0); j < validEdgeCnt; ++j) {			if (cnt == N - 2)break;			if (edges_valid[j].a == i || edges_valid[j].b == i)continue;			int a = findRoot(parents, edges_valid[j].a);			int b = findRoot(parents, edges_valid[j].b);			Union(a,b,ranks,parents,dates,cnt);		}//for j		if (cnt == N - 2) continue;		int costAll(0);		for (int j(0); j < M - validEdgeCnt; ++j) {			if (cnt == N - 2)break;			if (edges_invalid[j].a == i || edges_invalid[j].b == i)continue;			int a = findRoot(parents, edges_invalid[j].a);			int b = findRoot(parents, edges_invalid[j].b);			if (a != b) {				Union(a, b, ranks, parents, dates, cnt);				costAll += edges_invalid[j].cost;			}//if		}//for j		if (cnt == N - 2) {			if (costAll > maxCost) {				maxCost = costAll;				outputs.clear();				outputs.push_back(i);			}			else if (costAll == maxCost)outputs.push_back(i);		}		else {			if(maxCost!=INT_MAX)maxCost = INT_MAX, outputs.clear(), outputs.push_back(i);			else outputs.push_back(i);		}//if else	}//for i	if (maxCost == 0) {		puts("0");		return 0;	}//if	int size = (int)outputs.size();	for (int i(0); i < size-1; ++i)PRintf("%d ",outputs[i]);	if (size > 0)printf("%d/n",outputs[size-1]);	return 0;}//main
容易看出程序中的findRoot是遞歸函數(shù)。
2、封裝disjointSet類后，編寫主要業(yè)務(wù)邏輯代碼如下。
#include<stdio.h>#include<vector>using std::vector;#include<algorithm>using std::sort;#include<limits.h>struct edge {	int a, b;	int cost;	edge(int a_ = -1, int b_ = -1, int cost_ = -1) :a(a_), b(b_), cost(cost_) {}	bool operator<(const struct edge &x) const {		return cost < x.cost;	}//operator<};//disjointSet的定義int main() {	freopen("in.txt", "r", stdin);	int N(-1), M(-1);	scanf("%d%d", &N, &M);	vector<edge> edges_valid, edges_invalid;	int validEdgeCnt(0);	for (int i(0); i < M; ++i) {		int a(-1), b(-1), cost(-1), valid(-1);		scanf("%d%d%d%d", &a, &b, &cost, &valid);		if (valid == 1)edges_valid.push_back(edge(a, b, cost)), ++validEdgeCnt;		else edges_invalid.push_back(edge(a, b, cost));	}//for i	sort(edges_invalid.begin(), edges_invalid.end());	vector<int> outputs;	int maxCost(0);	for (int i(1); i <= N; ++i) {		disjointSet djset(N);		for (int j(0); j < validEdgeCnt; ++j) {			if (djset.getCount() == 2)break;			if (edges_valid[j].a == i || edges_valid[j].b == i)continue;			int aRoot = djset.findRoot(edges_valid[j].a - 1);			int bRoot = djset.findRoot(edges_valid[j].b - 1);			if (djset.isOneSet(aRoot, bRoot) == false)djset.unionSet(aRoot, bRoot);		}//for j		if (djset.getCount() == 2) continue;		int costAll(0);		for (int j(0); j < M - validEdgeCnt; ++j) {			if (djset.getCount() == 2) break;			if (edges_invalid[j].a == i || edges_invalid[j].b == i)continue;			int aRoot = djset.findRoot(edges_invalid[j].a - 1);			int bRoot = djset.findRoot(edges_invalid[j].b - 1);			if (djset.isOneSet(aRoot,bRoot)==false) {				djset.unionSet(aRoot, bRoot);				costAll += edges_invalid[j].cost;			}//if		}//for j		if (djset.getCount() == 2) {			if (costAll > maxCost) {				maxCost = costAll;				outputs.clear();				outputs.push_back(i);			}			else if (costAll == maxCost)outputs.push_back(i);		}		else {			if (maxCost != INT_MAX)maxCost = INT_MAX, outputs.clear(), outputs.push_back(i);			else outputs.push_back(i);		}//if else	}//for i	if (maxCost == 0) {		puts("0");		return 0;	}//if	int size = (int)outputs.size();	for (int i(0); i < size - 1; ++i)printf("%d ", outputs[i]);	if (size > 0)printf("%d/n", outputs[size - 1]);	return 0;}//main
注意觀察disjointSet定義在for(int i(1);i<=N;++i)循環(huán)里面。
下面給出disjointSet的定義
//quick-union//findRoot是近似O(1)的，里面采用的是路徑壓縮，用來得到集合序號(hào)，findRoot本身是遞歸實(shí)現(xiàn)的//isOneSet用來判斷xRoot和yRoot是否為同一集合。//unionSet是O(1)的，采用ranks來優(yōu)化的，用來合并xRoot到y(tǒng)Root里面//getDates用來得到該集合的元素個(gè)數(shù)。因此初始化全為1。dates還有別的用途。class disjointSet {private:	vector<int> parents, ranks, dates;	int cnt;public:	disjointSet(int size) {		cnt = size;		parents.resize(size);		for (int i(0); i < size; ++i)parents[i] = i;		ranks.assign(size, 0);		dates.assign(size, 1);		return;	}//disjointSet	inline int findRoot(int x) {		return parents[x] == x ? x : (parents[x] = findRoot(parents[x]));	}//findRoot	inline int getCount() {		return cnt;	}//getCount	inline bool isOneSet(int xRoot, int yRoot) {		return xRoot == yRoot;	}//inOneSet	void unionSet(int xRoot, int yRoot) {		if (ranks[xRoot] == ranks[yRoot])++ranks[yRoot];		if (ranks[xRoot] < ranks[yRoot])parents[xRoot] = yRoot, dates[yRoot] += dates[xRoot];		else parents[yRoot] = xRoot, dates[xRoot] += dates[yRoot];		--cnt;		return;	}//unionSet	inline int getDates(int x) {		return dates[x];	}//getDates};
注意該并查集的實(shí)現(xiàn) quick-union的，屬于類表示法。更符合面向?qū)ο蟮乃悸贰?/p>
下面是quick-find的disjointSet定義
//quick-find//findRoot是O(1)的，用來得到集合序號(hào)//isOneSet用來判斷xRoot和yRoot是否為同一集合。//unionSet是O(n)的，用來合并xRoot到y(tǒng)Root里面//getDates用來得到該集合的元素個(gè)數(shù)。因此初始化全為1。dates還有別的用途。class disjointSet {private:	vector<int> parents, dates;	int cnt, size;public:	disjointSet(int size) {		this->size = size;		cnt = size;		parents.resize(size);		for (int i(0); i < size; ++i)parents[i] = i;		dates.assign(size, 1);		return;	}//disjointSet	inline int findRoot(int x) {		return parents[x];	}//findRoot	inline int getCount() {		return cnt;	}//getCount	inline bool isOneSet(int xRoot, int yRoot) {		return xRoot == yRoot;	}//inOneSet	void unionSet(int xRoot, int yRoot) {		for (int i(0); i < this->size; ++i) {			if (parents[i] != xRoot)continue;			parents[i] = yRoot;		}//for i		dates[yRoot] += dates[xRoot];		--cnt;		return;	}//unionSet	inline int getDates(int x) {		return dates[x];	}//getDates};
注意到上面的disjointSet的實(shí)現(xiàn)里面的findRoot函數(shù)都是遞歸的，遞歸可能會(huì)造成函數(shù)調(diào)用棧的溢出。
findRoot還可以用while來實(shí)現(xiàn)，
下面這種最直觀，易懂。tmpVec來存儲(chǔ)中間結(jié)點(diǎn)，然后將tmpVec里面的點(diǎn)統(tǒng)統(tǒng)指向x。
但是由于findRoot調(diào)用頻率高，所以會(huì)頻繁產(chǎn)生tmpVec，雖然這個(gè)數(shù)組是在棧上開辟的，但是相應(yīng)的分配消耗還是存在。
int findRoot(int x) {//有個(gè)case是超時(shí)的。	vector<int> tmpVec;	while (x != parents[x]) {		tmpVec.push_back(x);		x = parents[x];	}//while	for (auto tmp : tmpVec)parents[tmp] = x;	return x;}//findRoot用上面的代碼替代disjointSet里面的findRoot遞歸實(shí)現(xiàn)。
這是由tmpVec導(dǎo)致的，所以采用了將x結(jié)點(diǎn)的父結(jié)點(diǎn)設(shè)置為它的爺爺結(jié)點(diǎn)這個(gè)策略。這個(gè)方法的壓縮幅度不太狠，但是總體看來，效果還算不錯(cuò)。
int findRoot(int x) {//那個(gè)超時(shí)解決了	while (x != parents[x]) {		//這行代碼也算是路徑壓縮，將x結(jié)點(diǎn)的父結(jié)點(diǎn)設(shè)置為它的爺爺結(jié)點(diǎn)。		parents[x] = parents[parents[x]];		x = parents[x];	}//while	return x;}//findRoot
3、其他優(yōu)化手段
關(guān)于ranks的那種優(yōu)化手段，效果不如findRoot里面路徑壓縮強(qiáng)。類似的壓縮手段還有很多，比如dates初始化為全1，里面的值表達(dá)該集合含有元素的個(gè)數(shù)，可以if(dates[xRoot]<=dates[yRoot])parents[xRoot]=yRoot;else parents[yRoot]=xRoot;這也是為了平衡一下這根樹，盡量讓“小樹”向“大樹”靠攏。