BOJ(백준) 6416 - 트리인가?

https://github.com/jongwuner/Algorithm/blob/master/BOJ/6416.cpp

---

아이디어

자세히 봐야 알지만 문제에서 '트리'까지는 명시를 해줬지만, 루트가 있는 트리(rooted tree)라는 정보는 숨겨주었다. 어느정도 트리를 경험해본 사람 입장에서는 빨리 캐치했을 것으로 보이지만, indegree가 없는 노드가 루트라는 것을 캐치해내야 한다.  

---

점검해볼 사항

- 트리의 정의 : 트리는 공집합도 트리이다.

- 루트가 있으면 방향성이 정해진다. (- 방향성이 정해져있는 트리라면, 루트가 있는 것)

- indegree가 두개일 수 없다

---

시간복잡도

O(t*N) : N은 트리의 노드 개수(에지개수 = 노드개수 - 1), t는 테스트케이스 갯수.

---

https://github.com/jongwuner/Algorithm/blob/master/BOJ/6416.cpp

#include<iostream>
#include<map>
typedef long long ll;
using namespace std;
map<ll, ll> M, indegree;
int main() {
    int testCases = 0;
    while (1) {
        bool ans = true;
        ll a, b;
        ll edgeCnt = 0;
        ll nodeCnt = 0;
        M.clear();
        indegree.clear();
        while (scanf("%lld%lld", &a, &b), (a || b)) {
            if (a == -1 && b == -1) return 0;
            edgeCnt++;
            if (M.find(a) == M.end()) 
                M.insert({ a, nodeCnt++ });
        
            if (M.find(b) == M.end()) 
                M.insert({ b, nodeCnt++ });
        
            if (indegree.find(b) == indegree.end()) 
                indegree.insert({b, 0});
            
            else ans = false;
        }
        if (edgeCnt > 0 && M.size() != edgeCnt + 1) ans = false;
        if (ans) printf("Case %d is a tree.\n", ++testCases);
        else printf("Case %d is not a tree.\n", ++testCases);
    }
    return 0;
}