4803: 트리

풀이 시간

• 1h

구현 방식

• 트리는 사이클이 발생하지 않는 그래프이다

• find-union을 통해 그래프를 찾아주는데, 해당 그래프에 사이클이 존재하는 지를 확인해주어야 한다

• 모든 간선을 순회하면서,
  1) find(a) != find(b)이면 union(a, b)를 호출해서 부모 합쳐주기
  2) find(a) == find(b)이면 cycle이 발생한 경우이므로 일단 cycle set에 해당 노드를 하나 추가해준다

• 기존에 만들어놓은 cycle set을 순회하면서, cycle_group에 cycle의 원소의 부모 노드들을 넣어준다

• 마지막으로 parent 리스트를 순회하면서, 원소가 cycle_group에 포함되지 않는다면 count += 1을 해준다

코드

import sys

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

T = 0
while True:
    N, M = map(int, sys.stdin.readline()[:-1].split())
    T += 1
    if N == 0 and M == 0: break

    edges = []
    for m in range(M):
        edges.append(list(map(int, sys.stdin.readline()[:-1].split())))

    parent = [i for i in range(N+1)]; cycle = set()
    for edge in edges:
        a, b = edge
        if find(a) != find(b):
            union(a, b)
        else: #cycle 발생
            cycle.add(b)
    
    for i in range(N+1): #parent 한번 갱신
        find(i)

    cycle_group = set()
    for c in cycle:
        cycle_group.add(parent[c])

    parent = set(parent[1:])
    count = 0
    for p in parent:
        if p not in cycle_group:
            count += 1

    print("Case " + str(T) + ": ", end="")
    if count == 0: print("No trees.")
    elif count == 1: print("There is one tree.")
    elif count > 1: print("A forest of " + str(count) + " trees.")

결과

• 다음 날 조금 더 최적화해서 다시 풀었다