BOJ 20530: 양분

 

www.acmicpc.net/problem/20530

20530번: 양분

 

 풀이 자체는 굉장히 쉽게 떠올렸는데 구현하는데 제법 애를 먹어 글로 남겨놓는다.

 

 문제를 간단하게 요약하자면 $N$개의 정점으로 이루어진 트리에 간선이 하나 추가된 그래프가 주어지고, $q$개의 쿼리가 주어진다. 쿼리는 $u,\ v$의 형태로 주어지며 두 정점 사이의 단순 경로의 개수를 구하는 문제이다.

 

 가장 간단한 접근 방법은 주어진 두 정점 $u,\ v$가 주어질 때마다 탐색을 하여 경로의 개수를 세어보는 방법이 있겠지만 탐색에 $O(N)$ 시간이 걸리므로 모든 쿼리를 처리하는데 $O(qN)$ 시간이 걸리므로 시간 내에 문제를 해결할 수 없다. 쿼리는 반드시 $q$번 수행해야 하기 때문에 시간을 줄일 수 없으므로 두 정점 사이의 경로의 개수를 세는 작업을 $O(N)$ 보다 빠른 시간 안에 해결해야만 한다.

 

 두 번째로 생각할 수 있는 접근은 $N$개의 정점으로 이루어진 트리에 간선이 하나 추가된다면 반드시 사이클이 한 개 존재한다는 점에서 힌트를 얻어, 사이클에 포함된 각 정점을 루트로 하는 트리가 달려있는 구조라고 생각한다면 쉽게 접근할 수 있다.  이 경우 두 정점 $u,\ v$ 사이의 경로를 크게 두 가지로 나눌 수 있다. 

 

1. 같은 서브트리 내에서 이동하는 경우
2. 특정 서브트리에서 다른 서브트리로 이동하는 경우

그림을 통해 자세히 살펴보도록 하자.

그림1: 예제 그래프

 그림의 그래프는 [1, 2, 3, 4]번 정점이 사이클을 이루고 있으며, 그 외의 정점은 사이클에 있는 한 정점을 루트로 갖는 서브트리에 포함된 정점들이다.

 

 첫 번째 경우의 한 예는 1번 정점을 루트로 하는 서브트리 내에서 이동하는 경우를 들 수 있다. 이 경우 트리의 특징 중 하나인, 두 정점 사이의 경로는 유일하다라는 점을 이용하면 항상 경로의 개수는 1임을 알 수 있다. [1, 5, 6, 7, 8] 중 어떤 정점을 선택하더라도 서브트리 밖으로 이동했다가 1번 정점을 거치지 않고 안으로 들어올 수 있는 방법이 없기 때문에 두 정점 사이를 이동할 때에는 항상 트리 안에서 이동이 이루어지기 때문이다.

 두 번째 경우는 사이클에 속한 정점, 즉 서브트리의 루트에서 두 곳으로 이동할 수 있기 때문에 항상 경로의 개수가 2임을 알 수 있다.

 

 먼저 사이클을 찾는 방법은 한번의 DFS만으로 쉽게 해결할 수 있다. 한 정점에서 출발하여 모든 정점을 순회하며 이전 정점이 아니며 이미 방문한 적이 있는 정점에 방문한 경우 해당 정점이 사이클의 시작이라고 판단하고 이전에 방문했던 모든 점들을 cycle 배열을 만들어 넣어주었다.

 

 사이클을 찾는 것은 그리 어렵지 않았지만 같은 서브트리에 포함되어 있는 정점인가를 확인하는 방법을 구현하기 위한 생각이 쉽게 떠오르지 않았다. 처음으로 구현한 방법은 사이클을 찾기 위해 한 번, 서브트리의 루트를 제외한 다른 정점 표시를 위해 두 번, 마지막으로 서브트리를 하나로 합치기 위해 세 번 사용하여 DFS를 무려 세 번이나 사용하였다.

#include<bits/stdc++.h>
using namespace std;
vector<int> adj[202020];
int chk[202020];
bool visited[202020];
vector<int> cycle;
map<int, int> connect;
int v1, v2;
void go(int s, int prev) {
	if (chk[s]) {
		v1 = s;
		cycle.push_back(s);
		return;
	}
	chk[s] = 1;
	for (int i = 0; i < adj[s].size(); ++i) {
		int nx = adj[s][i];
		if (nx == prev) continue;
		
		go(nx, s);
		
		if (v1 == -1) return;
		
		if (v1 == s) {
			v1 = -1;
			return;
		}
		
		if (v1 > 0) {
			cycle.push_back(s);
			return;
		}

	}
}
int go2(int s, int num) {
	if (chk[s]) return 0;
	chk[s] = num;
	for (int i = 0; i < adj[s].size(); ++i)
		go2(adj[s][i], num);
	return 2;
}
int c = -1;
void go3(int s) {
	if (visited[s]) return;
	visited[s] = 1;
	for (auto i : adj[s]) {
		if (chk[s] != 2 && chk[i] == 2)
			connect[chk[s]] = i;
		if (chk[s] == 2 && chk[i] != 2)
			connect[chk[i]] = s;
		go3(i);
	}
}
int main() {
	int n, q; scanf("%d %d", &n, &q);
	for (int i = 0; i < n; ++i) {
		int a, b; scanf("%d %d", &a, &b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	go(1, -1);
	memset(chk, 0, sizeof(chk));
	for (auto i : cycle) {
		chk[i] = 2;
		connect[i] = -1;
	}
	int cnt = -1;
	for (int i = 1; i <= n; ++i) 
		cnt -= go2(i, cnt);

	go3(1);

	for (int i = 0; i < q; ++i) {
		int u, v; scanf("%d %d", &u, &v);
		int cu = chk[u];
		int cv = chk[v];
		if (cu == cv && cu == 2)
			puts("2");
		else if (cu == cv)
			puts("1");
		else {
			if ((cu == 2 && connect[cv] == u) 
				|| (cv == 2 && connect[cu] == v)
				|| (connect[cu] == connect[cv]))
				puts("1");
			else
				puts("2");
		}

	}
}

 

일단 맞았습니다를 받고 생각해보니 루트를 따로 생각할게 아니라 한번에 묶어버리면 되겠다는 생각을 하여 아래와 같이 코드를 바꿔보았다. 속도 역시 훨씬 빠르다.

#include<bits/stdc++.h>
using namespace std;
vector<int> adj[202020];
int chk[202020];
bool visited[202020];
vector<int> cycle;
int v1;
void FindCycle(int s, int prev) {
	if (visited[s]) {
		v1 = s;
		cycle.push_back(s);
		return;
	}
	visited[s] = 1;
	for (int i = 0; i < adj[s].size(); ++i) {
		int nx = adj[s][i];
		if (nx == prev) continue;
		
		FindCycle(nx, s);
		
		if (v1 == -1) return;
		
		if (v1 == s) {
			v1 = -1;
			return;
		}
		
		if (v1 > 0) {
			cycle.push_back(s);
			return;
		}

	}
}
void MakeSubtree(int s, int num) {
	if (chk[s]) return;
	chk[s] = num;
	for (int i = 0; i < adj[s].size(); ++i)
		MakeSubtree(adj[s][i], num);
}
int main() {
	int n, q; scanf("%d %d", &n, &q);

	for (int i = 0; i < n; ++i) {
		int u, v; scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	FindCycle(1, -1);
	
	for (auto i : cycle)
		chk[i] = i;
	for (auto i : cycle) {
		chk[i] = 0;
		MakeSubtree(i, i);
	}
	

	for (int i = 0; i < q; ++i) {
		int u, v; scanf("%d %d", &u, &v);
		if (chk[u] != chk[v])
			puts("2");
		else
			puts("1");
	}
}