[백준 4195] 친구 네트워크 (C++)

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 987654321
using namespace std;


int N, M, F;
int parent[200001];
map<string, int> m;
//현재에는 자기 자신이 root임 

//루트 노드를 찾아주는 코드
int find(int a) {
	//a가 root임
	if (parent[a] < 0) return a;
	//a가 root가 아닐때 
	return parent[a] = find(parent[a]);

}

void merge(int a, int b) {
	a = find(a);
	b = find(b);

	if (a == b)return;
	//small to large
	if (parent[a] > parent[b]) swap(a, b);
	parent[a] += parent[b];
	parent[b] = a;
}

int main() {
	FASTIO;
	int T,cnt=1,tmp, out;
	string a, b;
	cin >> T;
	for (int k = 0; k < T; k++) {
		cin >> F;
		for (int i = 0; i < 200001; i++) parent[i] = -1;
		for (int f = 0; f < F; f++) {
			cin >> a >> b;
			if (m.find(a) == m.end()) {
				m.insert({ a,cnt });
				cnt++;
			}
			if (m.find(b) == m.end()){
				m.insert({ b,cnt });
				cnt++;
			}
			merge(m.find(a)->second, m.find(b)->second);
			tmp = find(m.find(a)->second);
			out = (-1) * parent[tmp];
			cout << out << "\n";
		
		}
		m.clear();
	}
}

Union Find 로 풀리는 문제이다.

 

이름이 string으로 주어지기 때문에 map을 사용해서 풀어야 한다.

 

그리고 친구 관계 수가 100000 개가 주어지기 때문에 parent 를 100001로 설정해서 두번 틀렸다.

친구 관계수가 100000개 라는것은 친구 수는 최대 200000명이 될 수 있기 때문에 200001로 설정해야만 한다.