백준 4803 트리 혼내주기

 

트리 문제를 많이 안풀어봐서 양방향 그래프라는걸 까먹고 삽질했다. 방문하지 않은 모든 정점에 대해서 bfs를 돌면서 트리인지 아닌지를 구별한다. 한 번의 bfs로 발견한 정점이 n개 일 때, 간선이 n-1개 라면 트리이다. 

 

출력에서 Case 뒤에 붙는 번호는 테스트 케이스 번호이다. 그리고 출력 형식에 'Case #: ~~' 이런식으로 숫자와 : 사이에 띄어쓰기가 없다는 걸 유의하자... 혹시 삽질하고 있다면 이 두가지를 참고해보길.

 

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

vector<bool> visited;
vector<int> adj[500];

int b(int src){
    int nodes = 0, vertices = 0;
    queue<int> q;
    q.push(src);
    visited[src] = true;
    while(!q.empty()){
        int from = q.front(); q.pop();
        nodes++;
        for(int to : adj[from]){
            vertices++;
            if(visited[to]) continue;
            q.push(to);
            visited[to] = true;
        }
    }
    return nodes-1 == vertices/2;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, u, v, cnt = 0;
    while(cin >> n >> m){
        if(!n && !m) break;
        cnt++;
        visited = vector<bool>(n, false);
        for(int i = 0; i < n; ++i) adj[i].clear();
        for(int i = 0; i < m; ++i){
            cin >> u >> v; --u; --v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        int trees = 0;
        for(int i = 0; i < n; ++i){
            if(visited[i]) continue;
            if(b(i)) trees++;
        }
        if(!trees) cout << "Case " << cnt << ": No trees.\n";
        else if(trees == 1) cout << "Case " << cnt << ": There is one tree.\n";
        else cout << "Case " << cnt << ": A forest of " << trees << " trees.\n";
    }
}