4803 트리

문제

https://www.acmicpc.net/problem/4803

4803번: 트리

 

접근

• 주어진 연결정보에 따라 노드를 분리하고 각 노드 집합에 대해 사이클이 발생하는지 확인하면 트리인지 아닌지 판별할 수 있으므로 유니온 파인드를 이용했다.
• 만약 사이클이 생긴다면 한 노드에서 다른 노드로 갈 수 있는 경로가 2개 이상이 되므로, 노드 집합의 원소의 개수가 k라고 한다면 노드 집합의 간선의 개수가 k-1보다 크다는 뜻
• 또한 노드를 연결정보에 따라 분리했으므로 사이클 조건만 만족한다면 루트 노드는 노드 안에서 항상 한개 이므로 따로 확인하지 않았다.

 

풀이

• 간선 정보를 입력받고 만약 사이클이 발생한다면 사이클이 발생한 노드의 부모 노드 정보를 저장한다.
• 이후 모든 노드들에 대해 부모 노드가 사이클이 발생한 노드가 아니라면 tree이므로 tree 집합에 저장한다.
• 고려할 반례는 이미 사이클이 존재하는 그래프에 새로운 노드를 연결할 경우, 해당 노드의 부모 노드 또한 사이클 집합에 추가해야 한다.

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 = 1
while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break

    parent = [i for i in range(n + 1)]
    cycle = set()

    for _ in range(m):
        a, b = map(int, input().split())
        x, y = find(a), find(b)

        if x == y:
            cycle.add(x)
        elif x in cycle or y in cycle:
            cycle.add(x)
            cycle.add(y)
        union(a, b)

    tree = set()
    for i in range(1, n + 1):
        x = find(i)
        if x not in cycle:
            tree.add(x)

    ans = len(tree)
    if ans == 0:
        print("Case {}: No trees.".format(t))
    elif ans == 1:
        print("Case {}: There is one tree.".format(t))
    else:
        print("Case {}: A forest of {} trees.".format(t, ans))
    t += 1