BOJ 4195 친구 네트워크

www.acmicpc.net/problem/4195

4195번: 친구 네트워크

 

친구의 관계가 주어진다. 예제를 보면

 

Fred Barney

Betty Wilma

Barney Betty

 

가 주어지는데 

 

Fred - Barney 가 연결되었으니 총 2명

Betty - Wilma 가 연결되었으니 총 2명

Barney - Betty 인데 Betty - Wilma, Barney - Fred 가 서로 친구이니 총 4명

 

즉, 집합이 주어지는데 같은 부모 노드 같은 구성원이 존재한다면 Union 시켜주면 된다.

다만 find 연산과 union 연산을 살짝 변형해줬는데 그냥 map을 쓰면 시간 초과가 난다.

따라서 unordered_map을 사용하면 O(1)에 처리할 수 있다.

 

string find(string x) {
	if (!m.count(x)) {
		m[x] = { x,1 };
	}
	if (m[x].first == x) return x;
	return m[x].first = find(m[x].first);
}

 

m.count(x) 로 x가 map에 존재하지 않는다면 크기 1로 생성해준다.

 

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

	if (a == b) return m[a].second;
	if (m[a].second < m[b].second) swap(a, b);
	m[a].second += m[b].second;
	m[b].first = a;
	return m[a].second;
}

 

병합하는 부분을 살펴보면 m[a].second와 m[b].second 를 비교해서 더 큰 집합에 작은 집합을 속하게 해 준다.

여기까지 이해했다면 입력받고 출력하는 건 쉽다.

 

#include <bits/stdc++.h>
using namespace std;

int tc, n;
unordered_map<string, pair<string, int>> m;

string find(string x) {
	if (!m.count(x)) {
		m[x] = { x,1 };
	}
	if (m[x].first == x) return x;
	return m[x].first = find(m[x].first);
}

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

	if (a == b) return m[a].second;
	if (m[a].second < m[b].second) swap(a, b);
	m[a].second += m[b].second;
	m[b].first = a;
	return m[a].second;
}

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

	cin >> tc;
	while (tc--) {
		cin >> n;
		m.clear();
		for (int i = 0; i < n; i++) {
			string a, b;
			cin >> a >> b;
			cout << merge(a, b) << '\n';
		}
	}

	return 0;
}