백준 4195번 _ 친구 네트워크

2020-06-26 · 배운 것 · 4분 읽기

https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

풀이방법

유니온 파인드에 size만 추가로 쓰면 되는데, 입력방식이 string이라 string을 키로 받고 value가 int인 map을 하나 선언해서 쓰면된다. c++에서 cin, cout을 쓰는 경우 cin.tie(NULL), ios::sync_with_stdio(false)를 꼭 쓰기바람.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

map<string, int> friendData;
int parents[100001];
int setSize[100001];
int n;

void parentsInit()
{
	for (int i = 1; i <= 10000; i++)
	{
		parents[i] = i;
		setSize[i] = 1;
	}
}

int getParents(int a)
{
	if (parents[a] == a) return a;
	else return parents[a] = getParents(parents[a]);
}

void UNION(int a, int b)
{
	a = getParents(a);
	b = getParents(b);
	
	if (a != b)
	{
		if (setSize[a] < setSize[b])
			swap(a, b);

		parents[b] = a;
		setSize[a] += setSize[b];
		setSize[b] = 0;
	}
}

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

	int testcase;
	cin >> testcase;

	for (int i = 0; i < testcase; i++)
	{		
		cin >> n;
		parentsInit();
		string first, second;
		int idx = 1;
		for (int j = 0; j < n; j++)
		{
			int firstIdx, secondIdx;

			cin >> first >> second;
			if (friendData.find(first) == friendData.end())
				friendData[first] = idx++;
			firstIdx = friendData[first];

			if (friendData.find(second) == friendData.end())
				friendData[second] = idx++;
			secondIdx = friendData[second];

			int firstParent = getParents(firstIdx);
			int secondParent = getParents(secondIdx);

			if (firstParent == secondParent)
				cout << max(setSize[firstParent], setSize[secondParent]) << '\n';
			else
			{
				UNION(firstIdx, secondIdx);
				firstParent = getParents(firstIdx);
				secondParent = getParents(secondIdx);
				cout << max(setSize[firstParent], setSize[secondParent]) << '\n';
			}
		}
		friendData.clear();
	}

	return 0;
}