👉 4803

문제

💡 문제 아이디어

• 트리는 사이클이 없는 요소이므로 이미 방문했던 노드에 다시 오는 경우에는 False 를 리턴해야한다

👀 풀이

# 4803

import sys

sys.setrecursionlimit(10**6)

c = 0

def f(node, prev) :
    if visited[node] : # 방문했다는 것은 cycle 인것 
        return False
    
    visited[node] = True # 방문 처리
    
    for i in graph[node] :
        if i!=prev : # 방향성이 없기 때문에 
            if not f(i,node) : # 사이클이 생기는 부분이라면 False 
                return False 
    return True
            

while True :
    c += 1
    tree = 0
    n,m = map(int, sys.stdin.readline().split())
    if n==0 and m==0 :
        break

    graph = [[] for _ in range(n+1)]
    
    for _ in range(m) :
        x,y = map(int, sys.stdin.readline().split())
        graph[x].append(y)
        graph[y].append(x)

    visited = [False for _ in range(n+1)]
    
    for i in range(1,n+1) :
        if visited[i] :
            continue
        if f(i,0) :
            tree += 1
    if tree == 0 :
        print(f"Case {c}: No trees.")
    elif tree == 1 :
        print(f"Case {c}: There is one tree.")
    else :
        print(f"Case {c}: A forest of {tree} trees.")