[BOJ] 트리인가?

[문제]

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

6416번: 트리인가?

[풀이]

6416

맞았습니다!!

1992

0

C++14 / 수정

822

45초 전

 

1) 트리의 성질 

노드의 개수  = 간선의 개수 +1 (루트는 나가는 간선밖에 없음)

간선이 하나도 없더라도 트리이다. (루트만 존재하는 경우)

 

---

#include <iostream>
#include <vector>
#include <set>
 
using namespace std;
 
//# 트리인가?
 
typedef pair<int, int> pp;
 
vector<pp> edges;
//노드는 간선 +1 
 
set<int> s;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    //u, v가 존재하는데 간선의 정보는 u-> v이다. 
    int u, v, idx = 1;
    while (1) {
        cin >> u >> v;
 
        if (u == 0 && v == 0){
            //트리인지 판단한다. 
 
            if (edges.size() + 1 == s.size() || edges.size() == 0) {
                cout << "Case " << idx << " is a tree.\n";
            }
            else {
                cout << "Case " << idx << " is not a tree.\n";
            }
            idx++;
            s.clear(); edges.clear();
        }
        else if (u == -1 && v == -1) break;
        else {
            //벡터에 간선 정보를 넣음 
            s.insert(u);
            s.insert(v);
            edges.push_back(pp(u, v));
 
        }
        //입력 그만 
        
    }
    return 0;
}