난이도: 골드 4
유형 : 트리
https://www.acmicpc.net/problem/4803

문제

그래프가 주어졌을 때, 각 연결 요소가 트리인지 판단하여, 전체 그래프 내에 트리의 개수를 출력하는 문제이다.

트리의 정의
: 사이클이 없는 연결 그래프

그리고 연결되어있는데 간선의 개수가 노드 -1 이라면 트리이다.

핵심 아이디어

BFS로 연결 요소 단위로 탐색한다
BFS는 시작 노드에서 출발해, 연결된 모든 노드만 탐색함.

즉, 하나의 연결 요소(Connected Component) 를 완전히 탐색

연결 요소마다 노드 수와 간선 수를 세고, 간선의 개수 = 노드 -1 인지 확인.

풀이 및 해답

import sys
from collections import deque


def bfs(start, graph, visited):
    queue = deque([start])
    visited[start] = True
    nodes, edges = 0, 0

    while queue:
        node = queue.popleft()
        nodes += 1
        for neighbor in graph[node]:
            edges += 1
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

    edges //= 2
    return nodes, edges


case_num = 1

while True:
    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):
        i, j = map(int, sys.stdin.readline().split())
        graph[i].append(j)
        graph[j].append(i)

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

    for node in range(1, n + 1):
        if not visited[node]:
            nodes, edges = bfs(node, graph, visited)
            if edges == nodes - 1:
                tree_count += 1

    if tree_count == 0:
        print(f"Case {case_num}: No trees.")
    elif tree_count == 1:
        print(f"Case {case_num}: There is one tree.")
    else:
        print(f"Case {case_num}: A forest of {tree_count} trees.")

    case_num += 1

BFS 를 통해 모두가 연결되어있는데? 간선의 개수가 노드-1 이면
-> 트리 임이 확실하다는 것을 배웠다.