BOJ 4803 - 트리 링크
(2023.09.14 기준 G4)

문제

그래프가 주어졌을 때, 트리의 개수 출력

알고리즘

DFS와 트리의 중요한 성질을 이용해 트리의 개수 찾기

풀이

트리는 '정점의 개수 = 간선의 개수 + 1'이라는 중요한 성질을 갖고 있다.
이를 이용해서 모든 정점을 하나씩 살펴보자.
만약에 아직 방문하지 않은 정점이라면, 그 정점에서 DFS를 시작해 방문 가능한 모든 정점을 찾자.
찾은 모든 정점의 간선의 개수를 세어 '정점의 개수 = 간선의 개수 + 1'가 성립하는지 확인하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500;

vector<int> graph[MAXN], vertex;
bool visited[MAXN];

void dfs(int i){
    visited[i] = true;
    vertex.push_back(i);

    for (int j: graph[i]) if (!visited[j]) dfs(j);
}

void init(int n){
    for (int i = 0; i < n; i++){
        graph[i].clear();
        visited[i] = false;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T = 1, n, m;
    for (cin >> n >> m; n; cin >> n >> m){
        cout << "Case " << T++ << ": ";
        init(n);

        // m개의 간선을 입력받아 그래프 완성
        for (int u, v; m; m--){
            cin >> u >> v;
            graph[--u].push_back(--v);
            graph[v].push_back(u);
        }

        int result = 0; // 트리의 개수
        for (int i = 0; i < n; i++){
            if (visited[i]) continue;

            // 방문하지 않은 정점에서 시작하여 방문 가능한 모든 정점을 찾는다.
            vertex.clear();
            dfs(i);

            // 방문한 정점들의 모든 간선 수를 세어서, 정점 개수 = 간선 개수 + 1이 성립하면 트리다.
            int edges = 0;
            for (int u: vertex) edges += graph[u].size();
            if (vertex.size() == edges / 2 + 1) result++; // 간선은 2개로 중복이 되어 있다.
        }

        // 트리 개수에 따라 결과 출력
        if (result == 0) cout << "No trees.\n";
        else if (result == 1) cout << "There is one tree.\n";
        else cout << "A forest of " << result << " trees.\n";
    }
}

• Python

import sys; input = sys.stdin.readline

def dfs(i):
    visited[i] = True
    vertex.append(i)

    for j in graph[i]:
        if not visited[j]:
            dfs(j)

T = 1
while True:
    n, m = map(int, input().split())
    if not n:
        break

    print('Case %d: ' % T, end = '')
    T += 1

    # m개의 간선을 입력받아 그래프 완성
    graph = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        graph[u].append(v)
        graph[v].append(u)

    result = 0 # 트리의 개수
    visited = [False] * n
    for i in range(n):
        if visited[i]:
            continue

        # 방문하지 않은 정점에서 시작하여 방문 가능한 모든 정점을 찾는다.
        vertex = []
        dfs(i)

        # 방문한 정점들의 모든 간선 수를 세어서, 정점 개수 = 간선 개수 + 1이 성립하면 트리다.
        edges = 0
        for u in vertex:
            edges += len(graph[u])
        if len(vertex) == edges // 2 + 1: # 간선은 2개로 중복이 되어 있다.
            result += 1

    # 트리 개수에 따라 결과 출력
    if result == 0:
        print('No trees.')
    elif result == 1:
        print('There is one tree.')
    else:
        print('A forest of %d trees.' % result)