[python] 4803 - 트리

4803번: 트리 (acmicpc.net)

4803번: 트리

 

정답률을 보고 겁을 먹었는데 간단한 문제였다.

입력으로 주어진 그래프에 트리가 있는지 판별하는 문제로,

중요한 것은 사이클이 존재하는지를 체크하는 것이다.

 

그래프가 존재하지 않을수도 여러개 존재할 수도 있기 때문에

union-find 알고리즘을 사용하여 루트노드를 기록하고

사이클이 존재하는지 체크하였다.

 

사이클이 존재할 경우 트리의 개수를 카운팅 하지 않는다.

 

# 4803 트리 - union find 사용

import sys 
input= sys.stdin.readline
flag = True

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

def union(v,u):
    root1=find(v)
    root2=find(u)
    
    if root1<root2:
        parent[root2] = root1
    elif root1>root2:
        parent[root1] = root2
    else:
        for i in range(len(parent)):
            if parent[i] == root1==root2:
                parent[i]=0
cnt = 0
while True:
    cnt+=1
    n,m = map(int, input().split())
    
    if n==0==m:
        break
    
    parent=[0] *(n+1)
    
    for i in range(n+1):
        parent[i]=i
    
    for i in range(m):
        a, b = map(int, input().split())
        union(a,b)
        
    rst=set()
    for i in range(1, n+1):
        if find(i) != 0:
            rst.add(find(i))
        
    size = len(list(rst))
    
    if size == 0:
        print("Case %d: No trees." % cnt)
    elif size == 1:
        print("Case %d: There is one tree." % cnt)
    else:
        print("Case %d: A forest of %d trees." % (cnt ,size))