[백준] 4196 친구 네트워크

문제 출처: https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

map<string,int>를 이용하여 아이디를 넣으면 임의로 설정한 고유한 번호가 나오도록 하여 다루기 쉽게 변경하였고 친구 관계가 생길 때마다 union 구조의 merge 연산으로 집합을 합치고 find 연산으로 집합의 크기를 구하여 출력하여 해결 할 수 있다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;

int arr[200001];
int find(int a) {
	if (arr[a] < 0)return a;
	return arr[a] = find(arr[a]);
}
void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)return;
	if (a < b) {
		arr[a] += arr[b];
		arr[b] = a;
	}
	else {
		arr[b] += arr[a];
		arr[a] = b;
	}
}

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


	int T;
	cin >> T;
	while (T--) {
		map<string, int>ma;
		int cnt = 1;
		fill(&arr[0], &arr[200001], -1);

		int F;
		cin >> F;
		for (int i = 0; i < F; i++) {
			string a, b;
			cin >> a >> b;
			if (ma[a] == 0) {
				ma[a] = cnt;
				cnt++;
			}
			if (ma[b] == 0) {
				ma[b] = cnt;
				cnt++;
			}
			merge(ma[a], ma[b]);
			cout << -arr[find(ma[a])]<<'\n';
		}

	}

}