[백준] 4803번: 트리

문제

백준 - 4803번: 트리

분석

그래프에 대한 정보가 주어졌을 때, 트리의 개수를 구하는 문제이다.

문제에서 주어진 그래프에 사이클의 유무가 트리의 개수를 세는 핵심이다.
사이클인지 판별하기 위해 Union-Find기법을 사용했다.
유니온 하려는 노드 둘의 대표노드가 같으면 사이클에 해당하는 그래프로 tmp에 넣어두고, 다를 경우 유니온 해줬다. 그래프가 확장되면서 대표노드는 바뀔 수 있기 때문에 tmp에 넣어뒀고, cycle이라는 set에 다시 중복되는 것을 제거해줬다.
cycle에 해당하지 않으면서 서로 다른 대표 노드들을 세주면 트리의 개수를 구할 수 있다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

def find(x):
    if x == uf[x]:
        return x
    uf[x] = find(uf[x])
    return uf[x]

def union(x, y):
    X = find(x)
    Y = find(y)
    if X != Y:
        uf[X] = Y

case = 1
while True:
    n, m = map(int, input().split())
    if (n, m) == (0, 0):
        break
    uf = [i for i in range(n+1)]
    tmp = []
    for _ in range(m):
        a, b = map(int, input().split())
        if find(a) != find(b):
            union(a, b)
        else:
            tmp.append(find(a))
    cycle = set()
    for x in tmp:
        cycle.add(find(x))
    trees = set()
    for i in range(1, n+1):
        x = find(i)
        if x not in cycle:
            trees.add(x)
    ans = len(trees)
    if ans == 0:
        print(f'Case {case}: No trees.')
    elif ans == 1:
        print(f'Case {case}: There is one tree.')
    else:
        print(f'Case {case}: A forest of {ans} trees.')
    case += 1

끝으로..

유니온 파인드 개념을 복습할 수 있던 좋은 문제였다.
다른 사람들의 풀이를 참고해보니 트리가 임의의 두 정점에 대해서 경로가 유일하다는 성질을 이용하여 dfs로 진행중 이미 방문한 곳을 방문하려고 하는 경우 사이클이 있다고 판별한 것 같다.