UVa 11503 Virtual Friends

想法：
　　架構與UVa 10685 Nature一樣，差別在於這題每輸入一組測資就要把該組測資所在的Set的大小輸出。

	#include <iostream>
	#include <map>
	#include <string>
	using namespace std;
	int Set[200010];
	int Num[200010];
	void Set_Initial(int N);
	int FindRoot(int x);
	void Union(int x, int y);
	int main()
	{
	ios::sync_with_stdio(false);
	int Case, F;
	cin >> Case;
	while (Case--) {
	cin >> F;
	map<string, int> Map;
	Set_Initial(2 * F);
	string A, B;
	for (int i = 0, j = 1; i < F; ++i) {
	cin >> A >> B;
	if (!Map[A]) Map[A] = j++;
	if (!Map[B]) Map[B] = j++;
	Union(Map[A], Map[B]);
	}
	}
	}
	void Set_Initial(int N)
	{
	for (int i = 0; i <= N; ++i) {
	Set[i] = i;
	Num[i] = 1;
	}
	}
	int FindRoot(int x)
	{
	if (x == Set[x])
	return x;
	return Set[x] = FindRoot(Set[x]);
	}
	void Union(int x, int y)
	{
	x = FindRoot(x);
	y = FindRoot(y);
	if (x != y) {
	Set[x] = y;
	Num[y] += Num[x];
	}
	cout << Num[y] << endl;
	}

view raw [UVa] 11503 Virtual Friends.cpp hosted with ❤ by GitHub