190202 BOJ 6416번 트리인가?

노드 u에서 v로 이동하는 경우는 유일하므로 key : v, value : u 로 잡고

'키가 중복으로 들어오는 경우, 트리가 아니다.' 식으로 문제를 풀었다.

그 과정에서 조건들을 꼼꼼히 생각하지 않아 시간이 좀 걸렸다.

1. 들어오는 간선이 하나도 없는 단 하나의 노드가 존재한다. 이를 루트(root) 노드라고 부른다.
2. 루트 노드를 제외한 모든 노드는 반드시 단 하나의 들어오는 간선이 존재한다.
3. 루트에서 다른 노드로 가는 경로는 반드시 가능하며, 유일하다. 이는 루트를 제외한 모든 노드에 성립해야 한다.

풀면서 실패했던 케이스들

1 2 2 1 0 0

양방향으로 간선이 있는 경우

1 2 2 3 3 4 4 1 0 0 

루트가 없으므로 트리가 아닌 경우

1 2 3 4 0 0

루트가 두 개 이상인 경우

 

통과 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#include <iostream> #include <map> #include <set> #define FOR(i,a,b) for(int i = a; i < b; i++) #define mp(a,b) make_pair(a,b) using namespace std; int main() {     int x, y, t = 1;     while (1) {         map<int, int> m;         set<int> s;         bool flag = true;         while (1) {             cin >> x >> y;             if (x < 0 && y < 0) return 0;             if (x == 0 && y == 0) break;             if (m.count(y) == 0) {                 if (m.count(x) == 1 && m.at(x) == y) flag = false;                 else {                     m.insert(mp(y, x));                     s.insert(x);                 }             }             else flag = false;         }         int cnt = 0;         for (int root : s) if (m.count(root) == 0) cnt++;         if (flag && cnt == 1 || s.empty()) cout << "Case " << t << " is a tree.\n";         else cout << "Case " << t << " is not a tree.\n";         t++;     } } Colored by Color Scripter

cs

코드를 더 단순하게 할 수 있을 거 같은데 고민을 해봐야겠다.