백준 트리_4803 [c++]

4803 트리 골드 4

문제

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

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 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.”를 테스트 케이스 번호와 함께 출력한다.

풀이

그래프를 인접리스트로 vector를 이용해 입력받은 후 bfs를 돌면서 방문했던곳을 재방문했다면 cycle로 판단할 수 있다.

vector에는 인접한 정점들이 모두 저장되기에 bfs에서 now와 next의 pair를 이용해 직전 부모는 제외하고 탐색한다.

코드를 작성하고 제출했는데 테스트케이스는 모두 맞는데 틀렸다고 나왔다. 다른 코드들을 살펴보니 풀이방법, 코드도 거의 유사해 틀린부분을 찾기 힘들었는데,

while문이 잘못되었었다.

n과 m모두 0인 경우 종료해야한다.

이 부분을 while(n != 0 && m != 0)으로 작성했는데

n과 m모두 0인 경우(n == 0 && m == 0)의 반대는 => (n != 0

m != 0) 이다.

기본적인 건데 실수하지 말자..

코드

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

vector<int> adj[501];
int visited[501] = { 0, };

void init(){
    for(int i = 0; i < 501; i++)
    {
        adj[i].clear();
        visited[i] = 0;
    }
}

int bfs(int start){

    int cycle = 0;
    queue<pair<int, int> > q;
    q.push(make_pair(start, -1));
    visited[start] = 1;

    while(!q.empty())
    {
        int now = q.front().first;
        int parent = q.front().second;
        q.pop();

        for(int i = 0; i < adj[now].size(); i++)
        {
            int next = adj[now][i];
            if(next != parent){
                if(visited[next]){
                    cycle = true;
                    break;
                }
                else{
                    q.push(make_pair( next, now ));
                }
            }
        }
        if(cycle) break;
    }
    if(cycle){
        return 0;
    } else{
        return 1;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    int cnt = 1;

    while(n != 0 || m != 0){

        int from, to;
        int tree = 0;
        for(int i = 0; i < m; i++)
        {
            cin >> from >> to;
            adj[from].push_back(to);
            adj[to].push_back(from);
        }
        // cout << "input done\n";
        for(int i = 1; i <= n; i++)
        {
            if(visited[i] == 0){
                if(bfs(i) == 1){
                    tree++;
                }
            }
        }
		string answer = "";
		if (!tree) {
			answer = "No trees.\n";
		}
		else if (tree == 1) {
			answer = "There is one tree.\n";
		}
		else {
			answer = "A forest of " + to_string(tree) + " trees.\n";
		}
		cout << "Case " << cnt << ": " << answer;
        cnt++;
        init();
        cin >> n >> m;
    }

}

• ps
• bfs