#302

중심 노드 찾기

부터 까지 번호가 매겨진 개의 노드가 있는 유향 단순 그래프(simple directed graph)가 있다.

이 중 한 노드가 진입 차수(in-degree)가 0이고, 진출 차수(out-degree)가 임이 보장되어 있다. 이 노드를 "중심 노드"라고 하자.

는 두 노드 와 에 대해 에서 를 향하는 방향성 간선()가 존재하는지 질의를 하는 함수이며, 이 질의에 대한 답은 yes (존재함) 또는 no (존재하지 않음)이다.

어떤 그래프에서도 중심 노드를 찾는 것을 보장하는 함수의 최소 호출 횟수는?

문제를 해결하려면 로그인해 주세요.

#302

부터 까지 번호가 매겨진 개의 노드가 있는 유향 단순 그래프(simple directed graph)가 있다.

이 중 한 노드가 진입 차수(in-degree)가 0이고, 진출 차수(out-degree)가 임이 보장되어 있다. 이 노드를 "중심 노드"라고 하자.

어떤 그래프에서도 중심 노드를 찾는 것을 보장하는 함수의 최소 호출 횟수는?

문제를 해결하려면 로그인해 주세요.