(BOJ) 15789 CTP 왕국은 한솔 왕국을 이길 수 있을까?

문제: https://www.acmicpc.net/problem/15789

 

문제 풀이:

동맹 왕국들 입력 받을 때마다 merge해주고 cnt[root]=(node 개수) 업데이트 해주기

각 동맹 왕국들의 루트와 동맹 왕국들의 수를 priority_queue에 저장

동맹 기회만큼 merge하는데 자기 자신의 그룹이거나 한솔 왕국 그룹과는 동맹 맺지 않고 그냥 pop

 

소스 코드:

typedef pair<int, int> P;
int n, m,p[100001],cnt[100001];
bool visit[100001];
vector<vector<int>> v;
priority_queue<P> res;

int find(int x) {
	if (p[x] < 0) return x;
	return p[x] = find(p[x]);
}
bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;

	p[a] = b;
	cnt[b] += cnt[a];
	return true;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n >> m;
	memset(p, -1, sizeof(p));
	v.resize(n + 1);
	for (int i = 1; i <= n; i++) cnt[i] = 1;
	for (int i = 0; i < m; i++) {
		int q, w;
		cin >> q >> w;
		merge(q, w);
	}
	for (int i = 1; i <= n; i++) {
		int t = find(i);
		if (visit[t]) continue;
		visit[t] = true;
		res.push({ cnt[t],t });
	}

	int a, b, c;
	cin >> a >> b >> c;

	for (int i = 0; i < c; i++) {
		while (!res.empty()) {
			int cur = res.top().second;
			res.pop();
			if (cur == find(b) || cur==find(a)) continue;
			merge(cur, a);
			break;
		}
	}

	cout << cnt[find(a)]<<'\n';
	return 0;
}