[BOJ 4803 / C++] 트리 (트리)

문제링크: https://www.acmicpc.net/problem/4803

 

1. 코드

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

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

    int tc = 1;
    while (true) {
        int n, m;
        cin >> n >> m;
        if (n == 0 && m == 0) break;

        vector<vector<int>> adj(n+1);
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        vector<int> vis(n+1, false);
        vector<int> parent(n+1, 0);
        
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (vis[i]) continue;
            
            bool isTree = true;
            queue<int> Q;

            Q.push(i);
            vis[i] = true;
            while (!Q.empty()) {
                int cur = Q.front(); Q.pop();
                for (int nxt: adj[cur]) {
                    if (nxt == parent[cur]) continue;
                    if (vis[nxt]) {
                        isTree = false;
                        continue; // 주의! break 아님!
                    }
                    Q.push(nxt);
                    vis[nxt] = true;
                    parent[nxt] = cur;
                }
            }
            if (isTree) cnt++;
        }

        cout << "Case " << tc << ": ";
        if (cnt == 0) {
            cout << "No trees.\n";
        }
        else if (cnt == 1) {
            cout << "There is one tree.\n";
        }
        else {
            cout << "A forest of " << cnt << " trees.\n";
        }
        tc++;
    }
}

 

 

2. 시간복잡도

n=500이고 m=1250이고 bfs의 시간복잡도는 O(v+e)이므로 O(tc * (2000)) 정도이다. test case의 개수는 나와있지 않지만 tc가 10^4개여도 10^8보다는 작기 때문에 1초 안에는 수행 가능할 것임을 예상해볼 수 있다. 

 

 

3. 분석

싸이클을 판단해서 트리인지 아닌지 판단하는 것이 중요하다. vis 배열과 parent 배열을 만들어서 nxt가 parent가 아니면서 방문한 적이 있으면 싸이클로 판단하면 된다.

 

또한 싸이클이 있어서 트리가 안된다고 판단하고 break를 해버리면 안되는 데 노드가 더 연결되어 있을 때 해당 노드들에도 vis 배열을 업데이트는 해줘야하기 때문이다. 백준에서 해당 부분을 break로 해도 정답처리는 되나 정확히는 continue로 처리하는 것이 올바른 bfs 코드이다.