문제배경

다윈의 종의기원이 출판 된 이래 1세기 반이 지나갔지만, 지구상의 생명체를 계통을 통합하는 Tree of Life 는 아직 완성되지 않았습니다.왜냐하면 90%의 생물이 아직 분류되지 않았기 때문입니다.

전체 Tree of Life를 한번에 그리기보다는 종들의 집합을 뭉쳐서 단순한 트리만듭니다. (이런 그룹 하나를 taxon이라고 부립니다. pl.taxa) 주어진 taxon의 집합을 이용해 계통(phylogeny) 수를 만들어 taxon간의 어떻게 진화해 왔는지를 Tree 형식으로 표현 할 수 있습니다.

문제해석

원문

An undirected graph is connected if there is a path connecting any two nodes. A tree is a connected (undirected) graph containing no cycles; this definition forces the tree to have a branching structure organized around a central core of nodes, just like its living counterpart. See Figure 2.

We have already grown familiar with trees in “Mendel's First Law”, where we introduced the probability tree diagram to visualize the outcomes of a random variable.

In the creation of a phylogeny, taxa are encoded by the tree's leaves, or nodes having degree 1. A node of a tree having degree larger than 1 is called an internal node.

Given : A positive integer n (n≤1000) and an adjacency list corresponding to a graph on n nodes that contains no cycles.

Return : The minimum number of edges that can be added to the graph to produce a tree.

해석

Tree란 graph에서 cycle이 존재하지 않고, 모든 노드가 연결되어 있지 않은 graph를 의미합니다. cycle하지 않다는 것음, 어떤 node $a_i$ 에서 node $a_j$로 통하는 path가 존재 할때, $a_i = a_j$인 path가 존재하지 않는 다는 의미입니다.

문제에서 주어지는 데이터는 첫번째로, 노드의 개수를 주어줍니다. 두번째로는 노드들의 edge를 주어줍니다.

Sample Dataset

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

주어지는 edge를 자세히 보면 노드수는 10개인데 주어지는 edge에 이어지는 node의 개수는 10개보다 적습니다. 위의 Sample Dataset에서는 3 번 노드가 존재하지 않습니다. 즉, 문제가 요구하는 것은 노드와 edge가 주어졌을 때, 아직 사용되지 않은 node를 이용하여 tree를 만들기 위한 edge의 개수를 구하라는 것입니다.

문제해결

문제를 해결하기위해서는 매우 간단한 지식만 알고 있다면 풀수 있습니다. tree 구조의 graph를 만들기 위해서 필요한 edge의 개수는 노드의 개수에서 1을 뺀 값이라는 것입니다. 즉, 위의 Sample Data에서 10개의 노드로 tree를 만들기 위한 최소한의 edge수는 9개가 됩니다. 그런데 주어진 edge의 개수는 6개 임으로, 필요한 최소한의 edge의 개수는 9 - 6 = 3 이 됩니다.

전체 코드는 github 에 올려놓았습니다.