백준 4195번 : 친구 네트워크 - Union & Find

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

4195번: 친구 네트워크

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>

using namespace std;

int unf[200002], sizes[2000002];

int Find(int x){
	if (x==unf[x]) return x;
	else return unf[x] = Find(unf[x]);
}

void Union(int a, int b){
	a = Find(a);
	b = Find(b);
	
	if(a!=b){
		if(sizes[a]<sizes[b]) swap(a,b);
		sizes[a] += sizes[b];
		unf[b] = a;
	}
}

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

	int t;
	cin >> t;
	for(int T=0; T<t; T++){
		int a;
		map<string, int> m;
		int node = 1;
		string s1, s2;
		cin >> a;
		
		for(int i=0; i<200002;i++){
			unf[i] = i;
			sizes[i] = 1;
		}
		
		
		for(int i=0; i<a; i++){
			cin >> s1 >> s2;
			if(m.count(s1)==0) m[s1]=node++;
			if(m.count(s2)==0) m[s2]=node++;
			
			Union(m[s1],m[s2]);
			
			
			cout << max(sizes[Find(m[s1])], sizes[Find(m[s2])]) << '\n';
			
		}
	}
	
	
}