[C/C++] 백준 4195번 - 친구 네트워크

 

 

<코드>

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

#define MAX 200000

int T, F;
int parent[MAX + 1];
int friend_num[MAX + 1];
string s1, s2;

int find(int u)
{
	if (u == parent[u]) return u;
	else return find(parent[u]);
}

void union_friend(int u, int v)
{
	u = find(u);
	v = find(v);

	if (u != v)
	{
		parent[u] = v;
		friend_num[v] += friend_num[u];
		friend_num[u] = 1;
	}

	cout << friend_num[v] << '\n';
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;

	while (T--)
	{
		cin >> F;
		// 변수 초기화
		int id = 1;
		map<string, int> m;
		for (int i = 1; i <= MAX; i++)
		{
			parent[i] = i;
			friend_num[i] = 1;
		}

		// id 기록하기
		for (int i = 1; i <= F; i++)
		{
			cin >> s1 >> s2;

			if (m[s1] == 0)
			{
				m[s1] = id++;
			}

			if (m[s2] == 0)
			{
				m[s2] = id++;
			}

			union_friend(m[s1], m[s2]);
		}
	}


}

 

풀이 방법

map<string,int> 의 경우 string을 KEY로 하고 VALUE값으로 id를 저장한다.

위의 캡쳐는 각각의 이름으로 id를 출력한 모습이다. 즉, 새로운 이름이 들어올 때마다 id를 부여하여 그 id를 이용하여 유니온 파인드를 하여 네트워크 친구 수를 구하였다.

 

 

 

www.acmicpc.net/problem/4195

4195번: 친구 네트워크