(C++) - 백준(BOJ) 6416번 : 트리인가?

https://www.acmicpc.net/problem/6416

6416번: 트리인가?

트리의 성질을 이해해 구현하는 문제였습니다.

 

풀이방법

 입력이 트리가 1개이며 연결 그래프임이 보장되므로 다음과 같은 2가지 성질에 주의해야합니다.

 

1. 트리는 정점의 개수 = 간선의 개수 + 1이어야 합니다. set을 이용해 정점을 저장하고 간선은 u와 v사이의 관계를 입력할 때마다 추가함으로써 구할 수 있습니다.

 

2. 트리는 사이클이 없어야합니다. 즉, 한 노드에서 출발해 그 노드로 돌아오는 경로는 없어야 합니다. 이는 bfs롤 통해 이미 체크한 정점을 다시 확인한다면 사이클이 존재함을 알 수 있습니다. 

 

* u, v를 0 0만 입력받은 경우 트리입니다.

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int testCase = 1;

int bfs(map<int,vector<int>> &treeMap){
    map <int,int> ckMap;

    for(auto t : treeMap)
        for(auto el : t.second)
            ckMap[el] = 1;

    int root = 0;
    for(auto t : treeMap)
        if(!ckMap[t.first]) 
            root = t.first;
    ckMap.clear();
    ckMap[root] = 1;
    queue <int> q;
    q.push(root);

    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = 0; i < treeMap[x].size(); i++){
            int nx = treeMap[x][i];
            if(ckMap[nx] == 1) return 0;
            ckMap[nx] = 1;
            q.push(nx);
        }
    }

    for(auto t : treeMap){
        for(auto el : t.second){
            if(!ckMap[el] || !ckMap[t.first]) return 0;
        }
    }
    return 1;
}

int main(){
    while(1){
        int edgeCnt = 0;
        map<int,vector<int>> treeMap;
        set <int> vertex;
        int u, v;
        while(1){
            cin >> u >> v;
            edgeCnt++;
            vertex.insert(u);
            vertex.insert(v);
            if(u == -1 && v == -1) return 0;
            if(u == 0 && v == 0) break;
            treeMap[u].push_back(v);
        }
        if(u && v && vertex.size() != edgeCnt + 1) printf("Case %d is not a tree.\n", testCase++);
        else{
            if(bfs(treeMap)) printf("Case %d is a tree.\n", testCase++);
            else printf("Case %d is not a tree.\n", testCase++);
        }
    }
}