#2258

그래프의 중심

방향 그래프 에서, 어떤 정점 가 중심 정점이라는 것은, 정점 에서 출발해서 2개 이하의 간선을 거쳐서 다른 모든 정점을 방문할 수 있다는 것이다.

위의 그래프는 중심 정점이 없는 그래프이며, 간선을 몇 개 추가해서 중심 정점이 있도록 만들려고 한다.

최소 몇 개의 간선을 추가해야 하는가?

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