[파이썬] 4803 트리

import sys
input = sys.stdin.readline

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

def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a != b:
        parent[max(a, b)] = min(a, b)
    edge_count[min(a, b)] = edge_count.get(min(a, b), 0) + 1

i = 1
while True:
    n, m = map(int, input().split())
    if not n + m:
        break
    parent = list(range(n))
    node_count, edge_count = {}, {}
    for _ in range(m):
        x, y = map(int, input().split())
        if x > y:
            x, y = y, x
        union_parent(x - 1, y - 1)
    for j, p in enumerate(parent):
        parent_p = find_parent(p)
        if p != parent_p and p in edge_count:
            edge_count[parent_p] += edge_count[p]
            del edge_count[p]
        parent[j] = p = parent_p
        node_count[p] = node_count.get(p, 0) + 1

    ans = 0
    for node in set(parent):
        if node not in edge_count or node_count[node] > edge_count[node]:
            ans += 1
    if ans == 0:
        print(f'Case {i}: No trees.')
    elif ans == 1:
        print(f'Case {i}: There is one tree.')
    else:
        print(f'Case {i}: A forest of {ans} trees.')
    i += 1

유니온파인드

1. 간선을 받아 union_parent 실행과 동시에 해당 부모를 key로하는 edge_count 1 증가

2. union을 한 결과 리스트인 parent의 각 원소의 개수를 세 node_count에 저장

3. 이 때 갱신되지 않은 parent가 있는 경우를 고려해 갱신이 되는 경우 부모의 edge_count에 더해주고 기존 키는 삭제

4. node가 edge_count에 없거나 (노드 한개로 구성되고 간선이 없는 트리), node_count가 edge_count보다 큰 경우(사이클이 존재하지 않는 트리) ans 1 증가

5. 출력

 

반례가 계속 나와서 여러번 틀린 문제