백준 4803 [트리] 파이썬

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

 

# 백준 4803 - 트리
import sys
from collections import deque
input = sys.stdin.readline

idx = 0  # 테스트 케이스 번호

while True:
    idx += 1  # 현재 테스트 케이스 번호 증가
    cnt = 0   # 트리의 개수를 셀 변수
    N, M = map(int, input().split())  # 정점 수 N, 간선 수 M

    if N == 0 and M == 0:  # 종료 조건
        break

    visited = [False for _ in range(N+1)]  # 정점 방문 여부
    graph = [[] for _ in range(N+1)]  # 인접 리스트로 그래프 표현

    # 간선 정보 입력
    for _ in range(M):
        A, B = map(int, input().split())
        graph[A].append(B)
        graph[B].append(A)

    # 각 정점마다 BFS로 연결된 컴포넌트를 탐색
    for i in range(1, N+1):
        if not visited[i]:
            cnt += 1  # 새로운 연결 요소 발견 → 일단 트리라고 가정하고 +1
            q = deque()
            visited[i] = True
            q.append((i, -1))  # (현재 노드, 이전 노드)
            flag = True  # 해당 연결 요소가 트리인지 여부

            while q:
                curr_node, prev_node = q.popleft()

                for next_node in graph[curr_node]:
                    if next_node != prev_node:  # 바로 이전에 왔던 노드는 무시
                        if visited[next_node]:
                            # 이미 방문한 노드를 다시 방문 → 사이클 존재
                            if flag:  # 처음 사이클을 감지한 경우에만
                                flag = False
                                cnt -= 1  # 트리가 아님 → 카운트 취소
                        else:
                            visited[next_node] = True
                            q.append((next_node, curr_node))

    # 트리 수에 따라 출력 포맷 변경
    if cnt == 0:
        print(f"Case {idx}: No trees.")
    elif cnt == 1:
        print(f"Case {idx}: There is one tree.")
    else:
        print(f"Case {idx}: A forest of {cnt} trees.")