# K. Milk Factory

### 문제 풀이 

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

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

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

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

```cpp
	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++)

```cpp
#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;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://tobigs.gitbook.io/usaco-week2/k.-milk-factory.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.