[코딩테스트] 기본반A 16일차

• 문제 이름: 트리(https://www.acmicpc.net/problem/4803)
• 문제 유형: 자료 구조, 그래프 이론, 그래프 탐색, 트리, 깊이 우선 탐색, 분리 집합
• 난이도: G4
• 언어: Python
• 문제 탐색하기
• 시간 복잡도
• 코드 설계하기
• 시도 회차 수정사항
• 정답 코드

import sys
sys.setrecursionlimit(10000)

def dfs(graph, visited, node):
    stack = [node]
    count_nodes = 0
    count_edges = 0
    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            count_nodes += 1
            for neighbor in graph[v]:
                count_edges += 1
                if not visited[neighbor]:
                    stack.append(neighbor)
    # 간선은 양방향이므로 실제 간선 수는 count_edges // 2
    return count_nodes, count_edges // 2

def solve_case(n, m, edges):
    # 그래프 구성
    graph = [[] for _ in range(n+1)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = [False] * (n+1)
    tree_count = 0

    for node in range(1, n+1):
        if not visited[node]:
            count_nodes, count_edges = dfs(graph, visited, node)
            # 트리 조건: 정점 수가 n이고 간선 수가 n-1이어야 한다
            if count_nodes - 1 == count_edges:
                tree_count += 1

    # 출력 형식에 맞게 결과 출력
    if tree_count == 0:
        return "No trees."
    elif tree_count == 1:
        return "There is one tree."
    else:
        return f"A forest of {tree_count} trees."

def main():
    case_number = 1
    while True:
        n, m = map(int, sys.stdin.readline().rstrip().split())
        if n == 0 and m == 0:
            break
        edges = [tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(m)]
        result = solve_case(n, m, edges)
        print(f"Case {case_number}: {result}")
        case_number += 1

main()