BOJ 12012 - Closing the farm (유니온파인드)

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

거꾸로 생각해서 쉬워지는 문제

 

<문제설명>

최대 2e5개의 정점과 간선으로 이뤄진 양방향 그래프가 주어진다. 정점의 개수를 n이라고 할때 쿼리가 n개 들어온다.

각 쿼리에선 정점이 하나 주어지는데(u), 현재 전체 컴포넌트의 수가 1이라면 YES를, 1이상이라면 NO를 출력한 후, 해당 정점과 정점에 연결된 간선을 모두 지운다.

 

<풀이>

문제 설명대로 완성된 그래프에 간선을 지워가면서 컴포넌트의 수를 log시간 이하로 구하는 것은 매우 어렵다. (불가능한 것 같다)

 

쿼리를 기록해두고 거꾸로 접근하면, 아무것도 없는 그래프에 정점과 연결된 컴포넌트를 이어주며 컴포넌트의 개수를 유지하는 문제로 바뀐다.

 

정점u를 추가할 때 이미 그래프에 추가된 정점들에 대해서만 merge를 해야 한다는 것에 유의하면 구현은 쉽다

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
#define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
using namespace std;
typedef long long ll;
const int MAX = 2e5 + 2;

int n, m, uf[MAX], chk[MAX], a[MAX],c;
vector<int> adj[MAX];
int find(int u) {
	if (uf[u] == -1) return u;
	return uf[u] = find(uf[u]);
}
bool merge(int u, int v) {
	u = find(u);
	v = find(v);
	if (u == v) return false;
	uf[u] = v;
	return true;
}

int main() {
	FAST;
	memset(uf, -1, sizeof(uf));
	cin >> n >> m;
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 0; i < n; i++) cin >> a[i];

	vector<bool> ans;
	for (int i = n - 1,u; i >= 0; i--) {
		c++; u = a[i];
		for (int v : adj[u]) 
			if (chk[v]) 
				if (merge(u, v))
					c--;
			
		chk[u] = true;
		ans.push_back(c == 1);
	}

	reverse(ans.begin(), ans.end());
	for (bool b : ans)
		cout << (b ? "YES\n" : "NO\n");
}

 

<생각>

 끝까지 생각이 안나서 solution 찾아봤던 문제