취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25172번 문제인 꼼꼼한 쿠기의 졸업여행이다.
문제는 아래 링크를 확인하자.

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

주어진 그래프에서 직접 노드를 하나씩 지워나가는 방식으로는 문제를 해결하기 어렵다. 대신, 그래프를 지워나가는 과정을 거꾸로 살펴 현재의 그래프로 채워나가는 과정으로 문제를 해결하자. 이는 disjoint set을 이용하여 편하게 구현할 수 있다.

구체적으로, 이번 i번째에 추가되는 노드가 x라 하면 지금까지 추가된 노드 중 x와 연결된 노드들을 disjoint set 자료구조를 x에 합치면서 x와 연결된 노드들의 개수를 같이 관리한다. 이 개수가 i와 같다면 현재 모든 노드들은 연결되어 있는 것이고 아니라면 연결되어있지 않은 상태라고 판단할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int N, M;
int uf[200001];
int cnt[200001];
int findf(int x) {
	if (x == uf[x]) return x;
	return uf[x] = findf(uf[x]);
}

vector<int> G[200001];

vector<bool> ans;
vector<int> qry;

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

	cin >> N >> M;
	while (M--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	ans.emplace_back(0);

	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		qry.emplace_back(x);
	}
	for (int i = 1; i <= N; i++) {
		int x = qry.back(); qry.pop_back();
		uf[x] = x, cnt[x] = 1;
		for (auto& node : G[x]) {
			if (uf[node]) {
				int fnode = findf(node);
				if (fnode == x) continue;
				uf[fnode] = x;
				cnt[x] += cnt[fnode];
			}
		}

		if (cnt[x] == i) ans.emplace_back(1);
		else ans.emplace_back(0);
	}

	while (!ans.empty()) {
		if (ans.back()) cout << "CONNECT\n";
		else cout << "DISCONNECT\n";
		ans.pop_back();
	}
}