[ 4803 ] [ Union-find ] 트리

문제 설명

---

문제

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

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 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. 입력받은 간선들을 순차적으로 방문하면서 각각의 간선들의 두 정점을 Union 해준다.
   • 이 때, 두 정점이 같은 그룹에 있는 경우 싸이클이 형성됨 => 트리가 아니란 걸 알 수 있음.
   • 맨 마지막에 처리하기 위해 두 정점중 하나의 정점을 따로 저장
2. (1)번에서 따로 저장해둔 정점이 어떤 그룹에 속해있는지 저장
   • 해당 그룹은 사이클이 형성된 그룹이므로 방문하지 않아야 함.
3. 전체 정점에 대해서, 방문하지 않은 그룹이면서 사이클이 형성되지 않은 그룹이라면
   • 해당 그룹 방문처리 / 정답 개수 하나 증가
4. 그룹 개수에 따라 다르게 print

---

소스 코드

---

import sys
from collections import deque

input = sys.stdin.readline

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])

    return parent[a]

def union(parent, a, b):
    p1 = find(parent, a)
    p2 = find(parent, b)
    if p1 != p2:
        if p1 > p2:
            parent[p1] = p2
        else:
            parent[p2] = p1

case = 0
while True:
    n, m = map(int, input().rstrip().split())
    if n == 0 and m == 0:
        break
    parent = [i for i in range(n+1)]
    cycle = []
    for _ in range(m):
        a, b = map(int, input().rstrip().split())
        p1 = find(parent, a)
        p2 = find(parent, b)
        if p1 != p2:
            union(parent, a, b)
        else:
            # cycle이 발생한 케이스이므로 따로 저장
            cycle.append(a)
    # 갱신
    for i in range(n+1):
        find(parent, i)

    # cycle이 있는 그룹들 저장
    group = set()
    for cycle_vertex in cycle:
        group.add(parent[cycle_vertex])

    answer = 0
    for i in range(1, n+1):
        if parent[i] in group:
            continue
        answer += 1
        group.add(parent[i])

    case += 1
    if answer == 0:
        print("Case %d: No trees."%(case))
    elif answer == 1:
        print("Case %d: There is one tree."%(case))
    else:
        print("Case %d: A forest of %d trees."%(case, answer))