K. Milk Factory

- iknoom1107(최문기)

문제 풀이

N개의 노드가 있을 때 N-1개의 노드(a)에서 모두 도달 할 수 있는 노드(b)를 출력하는 문제입니다.

이때 방향그래프의 간선의 방향을 반대로 바꾸면 문제가 간단해집니다.

간선의 방향 u -> v	간선의 방향 v -> u
모든 a에서 b에 도달 가능한가?	b에서 모든 a에 도달 가능한가?
N - 1번의 탐색	1번의 탐색

그래서 간선을 입력받을 때 이렇게 반대로 저장합니다.

	for (int i = 0; i < N - 1; i++) {
		int u, v;
		cin >> u >> v;
		f[v - 1][u - 1] = 1; // v -> u
	}

이제 N개 노드에 대해서 DFS나 BFS로 모든 노드에 도달 가능한지만 판단하면 끝입니다.

소스코드 (C++)

#include <iostream>
using namespace std;
bool vst[100];
int f[100][100];
int N;

int dfs(int u){
	int ret = 1;
	vst[u] = true;
	for (int v = 0; v < N; v++) {
		if(!vst[v] && f[u][v])
			ret += dfs(v);
	}
	return ret;
}

int main()
{
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int u, v;
		cin >> u >> v;
		f[v - 1][u - 1] = 1;
	}
	for (int i = 0; i < N; i++) {
		fill(vst, vst + N, false);
		if (dfs(i) == N) {
			cout << i + 1 << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}