백준 4803 - 트리 (파이썬)

Answer

import sys

input = sys.stdin.readline

def dfs(now, prev):
    visited[now] = True
    
    for next in tree[now]:
        if next == prev:
            continue
            
        if visited[next] == True:
            return False

        if dfs(next, now) == False:
            return False

    return True

case = 1

while True:
    n, m = map(int, input().split())

    if n == 0 and m == 0:
        break

    tree = [[] for _ in range(n + 1)]
    visited = [False] * (n + 1)
    
    for _ in range(m):
        x, y = map(int, input().split())
        tree[x].append(y)
        tree[y].append(x)

    count = 0
    for i in range(1, n + 1):
        if visited[i] == False:
            if dfs(i, 0) == True:
                count += 1

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

    case += 1