[백준 16402] 제국

문제

www.acmicpc.net/problem/16402

16402번: 제국

 

문제 풀이

1. 유니온파인드로 집합을 관리하기 위해 각 국의 이름을 입력받은 후 파싱하여 map에 <이름,인덱스>순으로 저장한다.

 

2. 위와 마찬가지로 각 국의 이름과 관계도 적절히 파싱한 후에 이기는 국가가 앞쪽으로 오도록 두 집합을 합쳐준다.

 

3. 합칠 때는 아래의 세가지 경우가 존재하고, 맨 위 두가지 경우는 같다고봐도 무방하다. (∵ 종주국 v의 부모는 pv)

• 종주국(u)이 종주국(v)을 이길 때 : u가 v의 속국으로 합쳐짐. $p[v]=u(=pu)$

• 종주국(u)이 속국(v)을 이길 때: v의 종주국과 그 속국들이 u의 속국으로 합쳐짐. $p[pv]=u(=pu)$

• 속국(u)이 종주국(v)을 이길 때: u의 종주국(v)가 u에 합쳐지고 u가 종주국이 된다. $p[v]=u$, $p[u]=-1$

4. 종주국은 부모가 음수이므로 정답에 부모가 음수인 것만 포함시킨다.

 

코드

#include <bits/stdc++.h>
using namespace std;
 
int n, m, pu, pv, a, b, idx;
string s;
char win;
vector<int> p;
map<string, int> mp;
vector<string> ans, v;
 
int find(int x) {
	if (p[x] < 0) return x;
	return p[x] = find(p[x]);
}
 
void merge(int u, int v) {
	pu = find(u), pv = find(v);
	if (pu == pv) p[v] = u, p[u] = -1;
	else p[pv] = pu;
}
 
int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);
 
	cin >> n >> m;
	cin.ignore();
	p.resize(n, -1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) cin >> s;
		v.push_back(s);
		mp[s] = i;
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < 3; j++) cin >> s;
		idx = s.find(',');
		a = mp[s.substr(0, idx)];
		for (int j = 0; j < 2; j++) cin >> s;
		idx = s.find(',');
		b = mp[s.substr(0, idx)], win = s[idx + 1];
		if (win == '2') swap(a, b);
		merge(a,b);
	}
	for (int i = 0; i < n; i++) 
		if (p[i] < 0) ans.push_back(v[i]);
	sort(ans.begin(), ans.end());
	cout << ans.size() << '\n';
	for (string i : ans) cout << "Kingdom of "<<i<<'\n';
}