[백준] 4803번 트리

문제 링크: https://www.acmicpc.net/problem/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."를 테스트 케이스 번호와 함께 출력한다.

문제 접근

tree 특징을 이용하는 문제이다.
트리는 node가 N개 존재한다면, edge는 n-1개 존재한다. 해당 특징을 이용하여, 문제를 풀면된다.
입력에서 두 노드중 어떤 노드가 부모노드인지 알 수 없기 때문에, 두 노드를 양방향으로 연결해준다.
주어진 그래프에서 dfs를 통해, 트리의 갯수를 찾아낸다. dfs를 하여, node의 갯수와 edge의 갯수를 얻어내, 만약 node -1 == edge / 2라면, tree의 갯수를 늘려준다.

코드 구현(c++)

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
vector<int> tree[501];
int checkNode[501];
int checkEdge[501];

int countNode(int n){
    checkNode[n] = true;
    int cnt = 1;
    for(int i = 0 ; i < tree[n].size() ; i++){
        if(!checkNode[tree[n][i]]){
            cnt += countNode(tree[n][i]);
        }
    }
    return cnt;
}

int countEdge(int n){
    int cnt = tree[n].size();
    checkEdge[n] = true;
    for(int i = 0 ; i < tree[n].size() ; i++){
        if(!checkEdge[tree[n][i]]){
            cnt += countEdge(tree[n][i]);
        }
    }
    return cnt;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int node, edge, tempNode1, tempNode2;
    int treeCnt, cnt;
    cnt = 0;
    while(1){
        cin >> node >> edge;
        if(node == 0 && edge == 0) break;
        cnt++;
        treeCnt = 0;
        memset(checkNode, false, sizeof(checkNode));
        memset(checkEdge, false, sizeof(checkEdge));
        for(int i = 0 ; i < edge ; i++){
            cin >> tempNode1 >> tempNode2;
            tree[tempNode1].push_back(tempNode2);
            tree[tempNode2].push_back(tempNode1);
        }
        for(int i = 1 ; i <= node ; i++){
            if(!checkNode[i]){
                int edgeNum = countEdge(i);
                int nodeNum = countNode(i);
                if(nodeNum - 1 == edgeNum / 2) treeCnt++;
            }
        }
        for(int i = 1 ; i <= node ; i++){
            tree[i].clear();
        }
        cout << "Case " << cnt << ": "; 
        if(treeCnt == 0) cout << "No trees.\n";
        else if(treeCnt == 1) cout << "There is one tree.\n";
        else cout << "A forest of " << treeCnt << " trees.\n";
    }

}