[백준 4803][C++] 트리 (Gold 4)

[문제보기]

4803. 트리

4803번: 트리

 

[풀이과정]

BFS 알고리즘을 사용하여 문제를 해결했다.

입력값으로 그래프를 생성한 후에 모드 노드에 대해 방문을 하면서 트리의 개수를 살펴본다.

이때 "간선/2 = 노드-1"이라는 공식을 사용하여 트리를 반별하는데, 무방향 그래프이기 때문에 

간선을 /2해준 것이다.

 

[소스코드]

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int n, m;

int main(){
    int tc = 0;
    while(1){
        cin >> n >> m;

        if(n == 0 && m == 0) return 0;

        vector<int> graph[501];
        bool visit[501];
        fill(visit, visit+501, false);

        int cnt = 0;

        for(int i=0; i<m; i++){
            int a, b; cin >> a >> b;

            graph[a].push_back(b);
            graph[b].push_back(a);
        }

        queue<int> q;
        for(int i=1; i<=n; i++){
            int edge = 0;
            int node = 0;

            if(visit[i] == false){
                q.push(i);
                cnt++;

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

                    if(visit[cur]) 
                        continue;

                    node++;
                    visit[cur] = true;

                    for(int j=0; j<graph[cur].size(); j++){
                        edge++;
                        q.push(graph[cur][j]);
                    }
                }

                if(edge/2 != node-1)
                    cnt--;
            }
        }

        if (cnt >= 2)
            printf("Case %d: A forest of %d trees.\n", ++tc, cnt);
        else if (cnt == 1)
            printf("Case %d: There is one tree.\n", ++tc);
        else
            printf("Case %d: No trees.\n", ++tc);

    }
}

 

[해결과정 중 실수한 부분]

블로그 참고...

www.crocus.co.kr/630