백준 g4 4803 트리 c++

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

4803번: 트리

 

문제

입력으로 주어진 그래프에 트리의 개수대로

No trees. / There is one tree. / A forest of 개수 trees. 를 출력하기

 

풀이

그래프가 트리가 되려면 모두 연결되어있어야 하고, 사이클이 없어야 한다.

그래프의 시작점에서 연결된 노드를 모두 탐색한다. 이때, 이미 탐색된 노드가 있다면 그것은 사이클이 있다는 뜻이므로 트리가 아니다.

 

전체 코드

/*boj g4 4803 트리*/
#include <iostream>
#include <queue>
#include <vector>
#define MAXN 502
using namespace std;

int N, M;

vector<int> adj[MAXN];
int p[MAXN];

void initialize() {
    for (int i = 0; i < MAXN; i++) {
        adj[i].clear();
        p[i] = 0;
    }
}

bool bfs(int start) {
    queue<int> Q;
    Q.push(start);

    while (!Q.empty()) {
        int cur = Q.front();
        Q.pop();

        for (int nxt : adj[cur]) {
            if (p[cur] == nxt) continue;
            if (p[nxt] != 0) return false;

            p[nxt] = cur;
            Q.push(nxt);
        }
    }
    return true;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 0;
    while (1) {
        cin >> N >> M;
        if (N == 0 && M == 0) break;
        T++;
        int answer = 0;
        initialize();

        for (int i = 0; i < M; i++) {
            int x, y;
            cin >> x >> y;

            adj[x].push_back(y);
            adj[y].push_back(x);
        }

        for (int i = 1; i <= N; i++) {
            if (p[i]) continue;

            if (bfs(i)) answer++;
        }

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