BOJ 4803번: 트리

문제 설명

트리의 개수를 세는 프로그램

🔗 문제 링크

핵심 아이디어

• 트리의 개수 세는 법 -> 사이클이 있는지 확인하기! (하나라도 있으면 안됨)
• 현재 cur에서 연결되어있는 nxt를 보면서 생길 수 있는 경우의 수
  • 방문 안함 -> 새로운 길로 계속 탐색
  • 방문 함 -> 부모임 -> 부모로 돌아가는 건 무시
  • 방문 함 -> 부모가 아님 -> 사이클! (또다른 길로 이미 왔던 곳에 도달)
• DFS를 이용해서 1에서 시작하여 사이클 있는지 확인하고 트리 개수 세기

코드

#include <bits/stdc++.h>
using namespace std;
vector<int> adj[505];
bool vis[505];

bool dfs(int cur, int par){
    vis[cur] = true;
    for(int nxt : adj[cur]){
        if (!vis[nxt]){
            if (dfs(nxt,cur)) return true; // 자식에서 사이클 발견
        }
        else if (nxt != par){
            return true; // 이미 방문했고 부모가 아닌데 다시 나오면 사이클
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m, a, b;
    int t = 0;
    while(true){
        t++;
        int ans = 0;
        cin >> n >> m;
        if (n == 0 && m == 0) break;
        
        for(int i = 1; i <= n; i++) adj[i].clear();
        for(int i = 1; i <= n; i++) vis[i] = false;
        for(int i = 0; i < m; i++){
            cin >> a >> b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        
        for(int i = 1; i <= n; i++){
            if (!vis[i]){
                bool cycle = dfs(i,0);
                if (!cycle) ans++;
            }
        }
        
        cout << "Case " << t << ": ";
        if (ans == 0) cout << "No trees.\n";
        else if (ans == 1) cout << "There is one tree.\n";
        else cout << "A forest of " << ans << " trees.\n";
    }
}