🔥

문제

윌리네 우유 공장은 원래 N개의 목장을 N-1개의 수송로를 이용하여 수레로 우유를 옮기고 있었습니다.
윌리는 컨베이어 벨트에 대한 이야기를 듣고서, N-1개의 수송로를 전부 컨베이어 벨트로 바꿨습니다, 하지만 컨베이어 벨트가 단방향으로만 움직인다는 사실을 몰랐던 윌리는 어느 목장에 우유 가공 센터를 세워야 모든 목장의 우유들을 우유 가공 센터까지 운반할 수 있을 지 고민을 하게 되었다.
윌리를 도와 어느 목장에 우유 가공 센터를 세워야 하는 지 출력해보자.

입력

첫 줄에 목장의 수 N이 주어집니다 (N은 100 이하의 자연수)
둘째 줄부터 N-1개 줄에 걸쳐 두 정수 p,q가 공백을 사이에 두고 주어집니다. 이는 p번 목장에서 q번 목장으로 우유를 운반할 수 있는 컨베이어 벨트가 있다는 것을 의미합니다.

출력

윌리가 몇 번 목장에 우유 가공 센터를 세워야 하는지 번호를 출력합니다. 만약 조건에 맞게 우유 가공 센터를 설립할 수 없다면 -1을 출력합니다.

예제 1 입력

3
1 2
3 2

예제 1 출력

2

예제 2 입력

10
6 1
10 7
3 6
7 2
9 8
1 5
2 3
4 5
8 5

예제 2 출력

5

Source

n = int(input())

edge = [[] for _ in range(n + 1)]
check = [0 for _ in range(n + 1)]

for i in range(n - 1):
	a, b = map(int, input().split())
	edge[b].append(a)

def dfs(edge, v):
	if(check[v] == 1):
		return 0
	check[v] = 1

	cnt = 1
	for u in edge[v]:
		cnt += dfs(edge, u)

	return cnt

cnt = 0
result = 0

for i in range(1, n + 1):
	for j in range(1, n + 1):
		check[j] = 0
	cnt = dfs(edge, i) - 1

	if(cnt == n - 1):
		result = i

if(result > 0):
	print(result)
else:
	print("-1")

참고