[baekjoon] 4803

트리 

문제

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

예제 입력

6 3
1 2
2 3
3 4
6 5
1 2
2 3
3 4
4 5
5 6
6 6
1 2
2 3
1 3
4 5
5 6
6 4
0 0

예제 출력

Case 1: A forest of 3 trees.
Case 2: There is one tree.
Case 3: No trees.

풀이

예제에서 Case 1이 3개의 트리를 갖는 이유는 단일 노드도 트리이기때문이다.

트리의 특성은 사이클이 생기면 안된다. 사이클이 생기지 않으려면 시작 노드로부터 한방향으로 뻗어 나갔을 때 지나온 노드를 다시 방문하지 않아야 한다.

이런 점을 탐색하기위해서 DFS를 사용했다. 

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <string.h>
#include <fstream>

using namespace std;

bool visit[501];
vector<int> edge[501];

int v, e;

void input(){
    int v1, v2;
    for(int i = 0; i < e; i++){
        cin >> v1 >> v2;

        edge[v1].push_back(v2);
        edge[v2].push_back(v1);
    }
}

void init(){
    for(int i = 1; i <= v; i++)edge[i].clear();
    memset(visit, false, sizeof(visit));
}
bool dfs(int cv, int prev){
    visit[cv] = true;
    for(auto nv : edge[cv]){
        if(nv == prev)continue;
        else if(visit[nv])return false;
        else if(!dfs(nv, cv)) return false;
    }
    return true;
}
int countTree(){
    int answer = 0;
    queue<int> q;

    for(int cv = 1; cv <= v; cv++){
        if(dfs(cv, 0))answer++;
    }

    return answer;
}

void solve(){
    int round = 1;
    while(true){
        cin >> v >> e;
        if(v == 0 && e == 0)break;
        init();
        input();
        int answer = countTree();
        
        if(answer > 1) printf("Case %d: A forest of %d trees.\n", round, answer);
        else if(answer == 1) printf("Case %d: There is one tree.\n", round);
        else printf("Case %d: No trees.\n", round);
        round++;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();
}