Completing a Tree(트리 완성시키기)

https://rosalind.info/problems/tree/

ROSALIND | Completing a Tree

Problem

Figure 2. A labeled tree with 6 vertices and 5 edges.

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 nn (n≤1000n≤1000) and an adjacency list corresponding to a graph on nn nodes that contains no cycles.

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

Sample Dataset

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

Sample Output

3

 

 이 문제는 몇 개의 간선을 추가한다면 트리가 다 이어지는지를 출력하는 문제이다. 이 뜻은 연결되지 않은 독립적인 트리들이 몇개가 있는지를 물어보는 것과 같다. 독립된 트리의 개수를 구하기는 DFS나 BFS를 통하여 풀 수 있다. 필자는 스택을 활용한 DFS로 이 문제를 풀었다.

def DFS(start,graph):
    visited=[]#방문
    stack=[]#방문할것

    stack.append(start)#시작
    while stack:#스택이 있는 한
        node=stack.pop()#스택에서 빼냄
        if node not in visited:#이 노드 미방문
            visited.append(node)#방문처리
            made.append(node)#글로벌 방문처리
            stack.extend(graph[node])#방문할 것들
    return visited
        

if __name__=='__main__':
    with open(r'파일경로','r') as fi:
        n=int(next(fi).rstrip())
        graph=[[] for i in range(n+1)]#그래프
        for i in fi:
            a,b=map(int,(i.rstrip()).split())
            graph[a]+=[b]
            graph[b]+=[a]


global made#글로벌 방문처리
made=[]

path=0
for k in range(1,n+1):
    if k not in made:#글로벌 미방문
        path+=1#추가
    	DFS(k,graph)

print(path-1)#필요한 간선은 독립된 트리보다 1개 적음