[BOJ/Python] 4803_트리

문제 출처:https://www.acmicpc.net/problem/4803

4803번: 트리

문제

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

예제 입력 1

6 3
1 2
2 3
3 4
6 5
1 2
2 3
3 4
4 5
5 6
6 6
1 2
2 3
1 3
4 5
5 6
6 4
0 0

예제 출력 1

Case 1: A forest of 3 trees.
Case 2: There is one tree.
Case 3: No trees.

---

풀이

 

각 케이스 별로 트리의 개수를 구하는 문제이다.

정점이 연결되어있으면 하나의 트리이며, 사이클이 존재하면 트리가 아니게 된다.

정점은 1번부터 n번까지 존재한다.

 

풀이는 다음과 같다.

1. 두 정점이 만약 현재 같은 트리에 속해있지 않다면, 연결하여 하나의 트리로 만든다. (루트 노드를 통일시킨다.)
2. 만약 현재 같은 트리에 속해 있다면, 연결하게 되면 사이클이 생기게 된다. 따라서 트리가 아니게 된다.
3. 이 경우, 루트 노드를 0으로 설정하여 해당 트리의 개수를 세지 않도록 한다.
4. 최종적으로 루트 노드의 개수를 센다. (루트 노드가 0인 경우는 개수에 포함하지 않는다.)

코드는 다음과 같다.

 

import sys
 
def find_parent(parent,x):
    if parent[x] != x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]
 
def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
 
    if a<b:
        parent[b] = a
    else:
        parent[a] = b
 
 
case = 0
while True:
    case+=1
    n,m = map(int,sys.stdin.readline().split())
    parent = [i for i in range(n+1)]
    if n == 0 and m == 0:
        break
    
    for _ in range(m):
        a,b = map(int,sys.stdin.readline().split())
 
        if find_parent(parent,a)!=find_parent(parent,b):
            union_parent(parent,a,b)
        else:
            union_parent(parent,a,0)
        
    root = set()
    for i in range(n+1):
        root.add(find_parent(parent,i))
 
    result = len(root)-1
    
    if result==0:
        print("Case ",case,": No trees.",sep='')
    elif result==1:
        print("Case ",case,": There is one tree.",sep='')
    else:
        print("Case ",case,": A forest of ",result," trees.",sep='')