[백준/BOJ] 백준 4195번 : 친구 네트워크

www.acmicpc.net/problem/4195

4195번: 친구 네트워크

map을 활용한 유니온 파인드를 통해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <map>
using namespace std;

int tc;
int f;
map<string, string> parent;
map<string, string>::iterator it;
map<string, int> rank_size;
map<string, int> num;

void Pre()
{
	parent.clear();
	rank_size.clear();
	num.clear();
}

string Find(string u)
{
	if (parent[u] == u)
		return u;

	return parent[u] = Find(parent[u]);
}

void Merge(string u, string v)
{
	u = Find(u);
	v = Find(v);

	if (rank_size[u] < rank_size[v])
	{
		num[v] += num[u]; //친구 네트워크의 인원을 추가한다
		parent[u] = v;
	}

	else
	{
		num[u] += num[v]; //친구 네트워크의 인원을 추가한다
		parent[v] = u;

		if (rank_size[u] == rank_size[v])
			rank_size[u]++;
	}

}

int Solve(string u)
{
	u = Find(u);

	return num[u];
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> tc;

	for (int t = 0; t < tc; t++)
	{
		Pre();
		cin >> f;

		for (int i = 0; i < f; i++)
		{
			string u, v;

			cin >> u >> v;

			pair<string, string> uu = make_pair(u, u);
			pair<string, string> vv = make_pair(v, v);

			pair<string, int> u_rank_size = make_pair(u, 0);
			pair<string, int> v_rank_size = make_pair(v, 0);

			pair<string, int> u_num = make_pair(u, 1);
			pair<string, int> v_num = make_pair(v, 1);

			parent.insert(uu);
			parent.insert(vv);

			rank_size.insert(u_rank_size);
			rank_size.insert(v_rank_size);

			num.insert(u_num);
			num.insert(v_num);

			if (Find(u) != Find(v))
				Merge(u, v);

			cout << Solve(u) << "\n";
		}
	}

	return 0;
}