對并查集資料結構的了解

并查集是一種樹形的資料結構，用于處理一些不相交集合的合并及查詢問題。常常在使用中以森林來表示，進行快速調整。

案例：朋友圈

題目描述：

假如已知有n個人和m對好友關系（存于數字r）。如果兩個人是直接或間接的好友（好友的好友的好友...），則認為他們屬于同一個朋友圈，請寫程式求出這n個人裡一共有多少個朋友圈。

假如：n = 5 ， m = 3 ， r = {{1 , 2} , {2 , 3} , {4 , 5}}，表示有5個人，1和2是好友，2和3是好友，4和5是好友，則1、2、3屬于一個朋友圈，4、5屬于另一個朋友圈，結果為2個朋友圈。

輸入：

輸入包含多個測試用例，每個測試用例的第一行包含兩個正整數 n、m，1=<n，m<=100000。接下來有m行，每行分别輸入兩個人的編号f，t（1=<f，t<=n），表示f和t是好友。 當n為0時，輸入結束，該用例不被處理。

輸出：

對應每個測試用例，輸出在這n個人裡一共有多少個朋友圈。

樣例輸入：

5 3

1 2

2 3

4 5

3 3

1 2

1 3

2 3

樣例輸出：

2

分析代碼的時間複雜度，空間複雜度，正确率和效率

Int friends(int n,int m,int* r[]);

int set[10001];
int find(int x) //帶路徑優化的并查集查找算法
{
	int i, j, r;
	r = x;
	while (set[r] != r)  //尋找此集合的代表
		r = set[r];
	i = x;
	while (i != r)  //使得r代表的集合中，所有結點直接指向人，即路勁壓縮
	{
		j = set[i];
		set[i] = r;
		i = j;
	}
	return r;
}
void merge(int x, int y) //優化的并查集歸并算法
{
	int t = find(x);
	int h = find(y);
	if (t < h)
		set[h] = t;
	else
		set[t] = h;
}
int friends(int n, int m, int*r[]) 
{
	int i，count;
	for (i = 1; i <= n; i++)//初始化并查集，各點為孤立點，分支數為n
		set[i] = i;
	for (i = 0; i < m; i++)//讀入r
		merge(r[i][0],r[i][1]);
	count = 0;
	for (i = 1; i <= n; i++)
	{
		if (set[i] == i)
			++count;
	}
	return count;
}
           

通過類的方法解決：

#include "vector"  
#include "string"  
#include "algorithm"  
#include <iostream>  
#include "stack"  
#include "map"
#include <cmath>  
using namespace std;
#define MAX 100
class UFSet
{
public:
	UFSet()
	{
		parent = new int[MAX];
	};
	~UFSet()
	{
		delete[] parent;
		parent = NULL;
	};
	void makeSet(int n);初始化每個元素的祖先  
	int findSet(int x);//找到元素x的祖先元素  
	void unionSet(int a, int b);//若兩個元素的祖先不同，則将x元素的祖先設定為y元素的祖先  
	int getSets(int n);//擷取集合數量  
private:
	int *parent;//存放祖先節點，例如x=parent[i]，元素i的祖先節點為元素x  
};
void UFSet::makeSet(int n) //初始化  
{
	//初始化每一個元素都各自為一個獨立的集合，其祖先均設定為自身  
	for (size_t i = 1; i <= n; i++)
		parent[i] = i;
}
int UFSet::findSet(int x)
{
	//找到元素所在的集合，也就是找到自己的最高的祖先，  
	//這也是判斷兩個元素是否在同一個集合中的主要依據。  
	if (parent[x] == x)//遞歸截止條件（最高祖先的祖先是其自身）  
		return x;
 
	parent[x] = findSet(parent[x]);//遞歸，最終找到x的最高祖先，并且沿途找到所有的最高祖先  
	return parent[x];
}
void UFSet::unionSet(int x, int y)
{
	//将x和y所在的集合進行合并，利用findSet()判斷x和y所在的集合是否相同，  
	//如果不同，則要把其中一個元素的祖先指向另一個元素的祖先。  
	int ux = findSet(x);//擷取節點x的祖先  
	int uy = findSet(y);
	if (ux != uy)  parent[ux] = uy;
}
int UFSet::getSets(int n)
{
	int count = 0;
	for (int i = 1; i <= n; i++)
	{//如果存在某一個節點的祖先是自身說明他是孤立的或者本身就是祖先  
     //其他一切情況說明在某一個集合中，隻有最高祖先才能擁有以自己為祖先的能力
		if (parent[i] == i)
			count++;
	}
	return count;
}
int main()
{
	int m, n;
	while (cin >> n )
	{
		if (n == 0) break;
		cin >> m;
		if (m >= MAX) break;
		UFSet uset;
		uset.makeSet(n);//初始化  
		//接收m對關系  
		int x = 0;
		int	y = 0;
		for (int i = 0; i<m; i++)
		{
			cin >> x >> y;//注：這裡數組下标代表人的對應編号  
			uset.unionSet(x, y);
		}
		cout << uset.getSets(n) << endl;
	}
	return 0;
}