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

在湟源等地區(qū)，都構建了全面的區(qū)域性戰(zhàn)略布局，加強發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務理念，為客戶提供成都網(wǎng)站建設、成都網(wǎng)站設計 網(wǎng)站設計制作按需求定制開發(fā),公司網(wǎng)站建設,企業(yè)網(wǎng)站建設,成都品牌網(wǎng)站建設,營銷型網(wǎng)站建設,外貿營銷網(wǎng)站建設,湟源網(wǎng)站建設費用合理。

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

這個問題可以通過數(shù)據(jù)結構中的并查集來實現(xiàn)。

   并查集

• 將N個不同的元素分成一組不相交的集合。

• 開始時，每個元素就是一個集合，然后按規(guī)律將兩個集合合并。

代碼如下：

UnionFindSet.h：

#pragma once

class UnionFindSet
{
public:
	UnionFindSet(int N)
		:_a(new int[N])
		,_n(N)
	{
		memset(_a, -1, N * 4);//將每一組初始的元素值設為-1
	}

	//找該元素的根
	int FindRoot(int x)
	{
		while (_a[x] >= 0)
		{
			x = _a[x];
		}

		return x;
	}

	//合并
	void Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);

		_a[root1] += _a[root2];//將元素2的根合并到元素1的根上
		_a[root2] = root1;//元素2的值設置為元素1
	}

	//合并后集合總數(shù)
	int Count()
	{
		int count = 0;
		for (size_t i = 0; i < _n; ++i)
		{
			if (_a[i] < 0)
			{
				++count;
			}
		}

		return count;
	}
protected:
	int* _a;//元素集合
	size_t _n;//元素個數(shù)
};

Test.cpp

#include 
using namespace std;
#include "UnionFindSet.h"

int GroupsOfFriends(int n, int m, int r[][2])
{
	UnionFindSet ufs(n+1);

	for (size_t i = 0; i < m; ++i)
	{
		int x1 = r[i][0];
		int x2 = r[i][1];
		ufs.Union(x1, x2);
	}
	
	return ufs.Count()-1;//元素集合從0開始，應減去0的集合
}

void Test()
{
	int r[][2] = {{1,2}, {1,3}, {4,5}};
	int count = GroupsOfFriends(5, 3, r);
	cout<
過程：
            
            
                        

            文章名稱：C++實現(xiàn)并查集            

            文章地址：http://weahome.cn/article/pedjpo.html