并查集的應用

• 定義

 并查集是一種樹型的數據結構，用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題。常常在使用中以森林來表示。

• 應用

 若某個朋友圈過于龐大，要判斷兩個人是否是在一個朋友圈，確實還很不容易，給出某個朋友關系圖，求任意給出的兩個人是否在一個朋友圈。 規定：x和y是朋友，y和z是朋友，那么x和z在一個朋友圈。如果x,y是朋友，那么x的朋友都與y的在一個朋友圈，y的朋友也都與x在一個朋友圈。

如下圖：

代碼：

//找朋友圈個數
//找父親節點
int FindRoot(int child1, int *_set)
{
	int root = child1;
	while (_set[root] >= 0)
	{
		root = _set[root];
	}
	return root;
}
//合并
void Union(int root1, int root2, int *&_set)
{
	_set[root1] += _set[root2];
	_set[root2] = root1;
}
int Friend(int n, int m, int r[][2])//n為人數，m為組數，r為關系
{
	assert(n > 0);
	assert(m > 0);
	assert(r);
	int *_set = new int[n];
	for (int i = 0; i < n+1; i++)
	{
		_set[i] = -1;
	}
	for (int i = 0; i < m; i++)
	{
		int root1 = FindRoot(r[i][0],_set);
		int root2 = FindRoot(r[i][1],_set);
		if ((_set[root1] == -1 && _set[root2] == -1) || root1 != root2)
		{
			Union(root1, root2, _set);
		}
	}
	int count = 0;
	for (int i = 1; i <= n; i++)
	{
		if (_set[i] < 0)
		{
			count++;
		}
	}
	return count;

}
//主函數
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include<assert.h>
#include"UnionFindSet.h"
int main()
{
	int r[][2] = { { 1, 2 }, { 2, 3 }, { 3, 4 }, { 5, 6 } };
	cout << Friend(6, 4, r) << endl;
	system("pause");
	return 0;
}