백준 6416번: 트리인가?

문제

문제 바로가기> 백준 6416번: 트리인가?

풀이

문제에서 요구하는 트리의 3가지 성질을 만족하도록 코드를 작성하였다. 아무리 봐도 잘못된 부분이 없다고 생각했는데 ||자리에 &&를 써놓아서 몇시간을 해맸다... 이런 실수 정말 오랜만이다 ^_^ 그래도 끝내 찾아내서 행복하다...

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

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int k=1;
    while(1){
        set<int> node;
        vector<pair<int, int>> edge;
        int u, v, edgecnt=0, maxnode=0, tmp;
        while(1){
            cin>>u>>v;
            if(u==0 && v==0) {
                if(edgecnt==0) {
                    cout << "Case " << k++ << " is a tree.\n";
                    continue;
                } break;
            }
            if(u<0 && v<0) return 0;
            edgecnt++; node.insert(u); node.insert(v);
            edge.push_back(make_pair(u, v));
            tmp = max(u, v); maxnode = max(tmp, maxnode);
        }
        int root=0, rootCnt=0;
        int cnt[maxnode+1]={};
        int way[maxnode+1][maxnode+1]={};
        for(int i=0; i<edgecnt; i++) {
            cnt[edge[i].second]++;
            way[edge[i].first][edge[i].second] = 1;
        }
        for(int i=0; i<edgecnt; i++){
            if(root!=edge[i].first && cnt[edge[i].first]==0){
                rootCnt++;
                root = edge[i].first;
            }
        }
        if(rootCnt!=1 || node.size()!=edgecnt+1) cout << "Case " << k++ << " is not a tree.\n";
        else{
            queue<int> q; q.push(root);
            int visitcnt=0;
            while(!q.empty()){
                int s = q.front(); q.pop(); visitcnt++;
                for(int i=0; i<maxnode+1; i++){
                    if(way[s][i]==1) q.push(i);
                }
            }
            if(visitcnt==node.size()) cout << "Case " << k++ << " is a tree.\n";
            else cout << "Case " << k++ << " is not a tree.\n";
        }
    }
}