[Gold IV] 트리 - 4083

 

[문제 위치]

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

[문제 풀이]

이 코드는 무방향 그래프에서 트리의 개수를 세는 프로그램이다. 입력으로 주어지는 그래프가 여러 개일 수 있으며, 각 그래프마다 몇 개의 트리로 이루어져 있는지를 판단한다.

트리란 사이클이 없고 연결된 그래프이며, 정점의 수가 간선 수 + 1이라는 특징을 가진다. 이를 이용해 DFS로 연결 요소를 순회하면서 해당 조건을 만족하면 트리로 판단한다.

각 연결 요소마다 DFS로 정점 수 v와 간선 수 e를 구하고, v == e + 1을 만족하면 트리로 간주해 개수를 센다. 이후 트리의 개수에 따라 "No trees.", "There is one tree.", 또는 "A forest of N trees." 형식으로 결과를 출력한다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
vector<vector<int>> Graph;
vector<int> vt;
int deg[505];
bool check[505];
int n, m, v, e;
 
void dfs(int x) {
    v += 1;
    check[x] = true;
    vt.push_back(x);
    for (int i = 0; i < Graph[x].size(); i++) {
        int next = Graph[x][i];
        if (!check[next])     dfs(next);
    }
}
int main() {
    int c = 1;
    while (scanf(" %d %d", &n, &m) != -1) {
        if (n == 0 && m == 0) return 0;
        memset(check, 0, sizeof(check));
        memset(deg, 0, sizeof(deg));
        Graph.resize(n);
        for (int i = 0; i < m; i++) {
            int a, b; scanf(" %d %d", &a, &b);
            a--; b--;
            Graph[a].push_back(b);
            Graph[b].push_back(a);
            deg[a]++; deg[b]++;
        }
 
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (check[i]) continue;
            v = 0, e = 0;
            vt.clear();
            dfs(i);
            for (int i = 0; i < vt.size(); i++) e += deg[vt[i]];
            e /= 2;
            if (v == (e + 1)) ans += 1;
        }
        
        printf("Case %d: ", c++);
        if (ans == 0) puts("No trees.");
        else if (ans == 1) puts("There is one tree.");
        else printf("A forest of %d trees.\n",ans);
        Graph.clear();
    }
}