BOJ 25172 꼼꼼한 쿠기의 졸업여행

문제 링크입니다.

삭제하는 건 싫으니까 합치기에 올인하려 합니다

이상적인 여행 지도는 단일 연결 요소를 이루어야 합니다.

어떤 그래프가 주어졌을 때, 그래프에서 정점을 지워나가면서 그때마다 연결 상태를 판정하는 건 좀 귀찮습니다. 갱신될 만한 값이 많아서…

하지만 그래프에 정점을 추가해 가면서 서로 이어붙이는 건 상대적으로 간단합니다. 분리 집합과 같은 자료 구조를 활용하면 매우 빠르게 작동하기도 하고요.

그래서, 주어진 지울 정점 리스트의 순서를 뒤집어서 합치기를 진행할 겁니다. 하나씩 그래프에 추가하면서, 그 정점과 이어지는 간선 중 이미 그래프에 추가된 정점과 이어지는 간선이 있다면 서로 연결하는 식으로요. 이때 그래프가 단일 연결 요소인지는 새로 추가한 정점이 포함된 연결 요소의 크기가 현재까지 추가한 정점의 개수와 같은지를 보는 것으로 바로 알 수 있습니다. 분리 집합을 구현할 때 집합의 크기를 관리할 수 있게 Union by Size를 써 주면 쉽게 해결할 수 있습니다.

문제 순서를 뒤집어서 풀었으니, 구한 답 역시 반대로 출력해야 함에 유의해 주세요.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<int>> e;
bool vis[234567];

int par[234567];
int F(int x){
	return par[x] < 0 ? x : par[x] = F(par[x]);
}
void U(int u, int v){
	u = F(u); v = F(v);
	if(u == v) return;
	if(par[u] < par[v]){
		par[u] += par[v];
		par[v] = u;
		return;
	}
	par[v] += par[u];
	par[u] = v;
	return;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n, m; cin >> n >> m; e.resize(n+1); while(m--){
		int u, v; cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	stack<int> s; for(int i = 1; i <= n; i++){
		int x; cin >> x; s.push(x);
	}
	stack<bool> ss;
	memset(par, -1, sizeof(par));
	for(int i = 1; i <= n; i++){
		int now = s.top(); s.pop();
		vis[now] = 1;
		for(auto nxt : e[now]) if(vis[nxt]) U(now, nxt);
		ss.push(par[F(now)] == -i);
	}
	while(ss.size()){
		cout << (ss.top()?"CONNECT":"DISCONNECT") << '\n';
		ss.pop();
	}
	cout << "DISCONNECT";
}