頂級pat1014

利用并查集查環，之後深度優先周遊。注意朋友圈的直徑為兩個最遠的朋友之間所夾雜的朋友數。代碼如下：

#include <iostream>
#include<unordered_map>
#include<algorithm>
#include<set>
#include<vector>
#include<queue>
using namespace std;

vector<set<int>>friends;

template<class T>
class DisjointSets
{
public:
	unordered_map<T, T>father;
	T findFather(T x)
	{
		if (father[x] == x)
			return x;
		else
			return father[x] = findFather(father[x]);
	}
public:
	/*将元素x加入到元素_set所在的集合中*/
	DisjointSets() = default;
	inline void insert(T x)
	{
		father[x] = x;
	}

	inline bool find(T x)
	{
		return father.find(x) != father.end();
	}

	inline void set_union(T _set1, T _set2)
	{
		father[findFather(_set1)] = findFather(_set2);
	}

	inline bool isInTheSameSet(T x, T y)
	{
		return findFather(x) == findFather(y);
	}
};

int getDiameter(int beh)
{
	set<int>visited;
	queue<int>q;
	q.push(beh);
	visited.insert(beh);
	//cout << beh << ":" << endl;
	int dia = -2;
	while (!q.empty())
	{
		//cout <<"diameter "<<dia<< endl;
		int s = q.size();
		for (int i = 1; i <= s; i++)
		{
			auto top = q.front();
			q.pop();
			for (auto c : friends[top])
			{
				if (visited.find(c) == visited.end())
				{
					//cout << c << " ";
					q.push(c);
					visited.insert(c);
				}
			}
		}
		dia++;
	}
	return dia;
}

int main()
{
	DisjointSets<int>sets;
	int n;
	cin >> n;
	friends.resize(n + 1);
	for (int i = 1; i <= n; i++)
		sets.insert(i);
	for (int i = 1; i <= n; i++)
	{
		int m;
		cin >> m;
		for (int j = 0; j < m; j++)
		{
			int tmp;
			cin >>tmp;
			friends[i].insert(tmp);
			friends[tmp].insert(i);
			sets.set_union(i, tmp);
		}
	}
	set<int>behalf;
	for (int i = 1; i <= n; i++)
		behalf.insert(sets.findFather(i));
	cout << behalf.size()<<" ";
	int dia = 0;
	/*for testing*/
	//for (int i = 1; i <= n; i++)
		//cout << i << ":" << friends[i] << endl;
	//cout << endl;
	for (auto c:behalf)
	{
		//cout <<i<<" "<< getDiameter(i) << endl;
		dia = max(dia, getDiameter(c));
	}
	cout << dia;
	//print number,largest
	system("pause");
	return 0;
}

/*
4
1 2
2 1 3
2 1 2
0
*/