[C++] 백준 4803번 트리

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

풀이

트리 순회 시 dfs를 이용하였다. 사이클을 형성하는지 확인하기에 bfs는 적절하지 않다. dfs는 직전에 탐색한 부모 노드를 기억해두고, 현재 탐색하는 노드가 1) 직전 노드가 아니며 2) 방문한 적 없는 노드인지 확인하여 사이클을 만드는지 아닌지 알 수 있다.

코드

#include <iostream>
#include <vector>
using namespace std;

void printResult(int cnt, int t) {
    cout << "Case " << t << ": ";
    switch(cnt) {
        case 0: cout << "No trees."; break;
        case 1: cout << "There is one tree."; break;
        default: cout << "A forest of " << cnt << " trees."; break;
    }
    cout << "\n";
    return;
}

void dfs(bool& cycle, int cur, int prev, vector<vector<int>>& graph, vector<bool>& visited) {
    if(visited[cur]) {
        cycle = true;
        return;
    }
    
    visited[cur] = true;
    for(int next : graph[cur]) {
        if(next == prev) continue;
        dfs(cycle, next, cur, graph, visited);
    }
    
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int n, m, a, b, t=0;
    while(++t) {
        cin >> n >> m;
        if(!n && !m) break;
        
        vector<vector<int>> graph(n+1);
        for(int i=0; i<m; i++) {
            cin >> a >> b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        
        int cnt = 0;
        vector<bool> visited(n+1, false);
        
        for(int i=1; i<=n; i++) {
            if(visited[i]) continue;
            
            bool cycle = false;
            dfs(cycle, i, 0, graph, visited);
            
            if(!cycle) cnt++;
        }
        
        printResult(cnt, t);
    }
    
    return 0;
}