本篇博文旨在介紹一種數據結構——并查集；本文介紹了該數據結構的使用場景，并用代碼進行了實現該數據結構

朋友圈問題：

1、已知，有n個人和m對好友關系(存于一個集合r中)

2、如果兩個人是直接的或者間接的好友（好友的好友的好友。。。），那么他們屬于一個集合，就是一個朋友圈里的

3、寫出程序，求這n個人中一共有多少個朋友圈

文字描述還不明白的童鞋，可以看下面這個例子

例如：

n = 5 m = 3   

r = { { 1 , 2 },{ 2 , 3 },{ 4 , 5 } }

五個人有三對朋友關系

根據 集合r  我們可以看出1 、 2 、3 屬于一個朋友圈，4和5屬于一個朋友圈

所以結果有兩個朋友圈

由于之前學習過哈希表

所以就想出了這樣的解法

建立一個長度為n+1的數組（可以利用vector）

對應下標代表的是該人

然后遍歷一遍 集合r  比如（1,2）就將2掛到1節點的后面

最后我們遍歷一遍該數組，從1鏈接的節點中找到2，然后去找下標為2的數組鏈接的數字3，再找3，然后3沒有鏈接節點，則表示是一個朋友圈

依次輪推，可以算出兩個朋友圈

這個方法的確可行

但是，當關系量稍微復雜點就不好使了

其實7個人同屬于一個朋友圈，但是1-2結束，就多算一個朋友圈

而且，由于處理不當還出現了循環的問題，比如1-2-3-1

當然，這種情況可以通過加以處理來避免

但是這樣也太復雜了

有沒有一種簡便的方法來處理這個問題呢？

這里引入這次要介紹的數據結構——并查集

并查集

基本概念

將N個不同的元素分成互不相交的集合

然后按照規律將兩個集合進行合并

基本思想

1、首先我們建立n個大小的數組，分別代表人的序號

將數組的所有值初始化為 -1 ，代表各自屬于各自的集合

2、根據 集合r 對數組元素的值進行修改

比如 {0,6}

將a[0] 的值加上 a[6]的值

然后將a[6]所存的值改為 a[0]的下標 0 

修改后的下標如下圖所示

下面，如果0和4產生了關系，{0,4}

那么找到4的根（為1），將a[1]的值加到a[0]上，然后將a[1]的值改為a[0]的下標0

通過對數組元素的遍歷，只要值小于0，即代表為一個集合（朋友圈）中

代碼實現

#PRagma once#include<iostream>using namespace std;#include<vector>//定義并查集class UnionFindSet{public:	//構造函數，將初始值置為-1	//并進行擴容	UnionFindSet(size_t n)	{		v.resize(n+1, -1);	}	//找到根節點	size_t FindRoot(size_t x)	{		size_t ret = x;		while (v[ret] >= 0)			ret = v[ret];		return ret;	}	//將兩個人的朋友圈進行合并	void Union(size_t x1,size_t x2)	{		size_t root1 = FindRoot(x1);		size_t root2 = FindRoot(x2);		//同根，已經在一個集合		if (root1 == root2)			return;		v[root1] += v[root2];		v[root2] = root1;	}	//判斷是否在一個集合	bool IsInSet(int x1, int x2)	{		return FindRoot(x1) == FindRoot(x2);	}	//求集合(朋友圈)的個數	size_t SetSize()	{		size_t count = 0;		for (size_t i = 0; i < v.size(); ++i)		{			if (v[i] < 0)				count++;		}		return count-1;	}protected:	vector<int> v;};void TestUnionFindSet(){	//五個人，四個人有朋友圈關系	const int n = 5;	const int m = 4;	UnionFindSet ufs(n);	int r[m][2] = { { 1, 2 }, { 2, 3 }, { 4, 5 }, { 2, 4 } };	for (size_t i = 0; i < m; ++i)	{		ufs.Union(r[i][0], r[i][1]);	}	cout << "朋友圈的個數為:" << ufs.SetSize() << endl;}
代碼的GitHub鏈接
https://github.com/haohaosong/DataStruct/blob/master/UnionFindSet.h