6416 트리인가?

이건 할 수 있을 것 같은데...?

 

트리 조건이 세 개가 주어졌으니깐 세 조건 하나씩 확인하면 될 것 같다. 

 

1. 들어오는 간선이 하나도 없는 단 하나의 노드가 존재한다.

 > map 같은 걸 만들어서 들어오는 화살표 없는 노드가 하나인지 확인한다.

 

2. 루트 노드를 제외한 노드는 단 하나의 들어오는 간선이 존재한다.

 > 이것도 위의 map으로 확인하면 될 듯 

 

3. 루트에서 다른 노드로 가는 경로는 반드시 가능하며, 유일하다. 

> 경로가 두 개라면 fail.. 이까지 오면 트리 형식은 갖췄다는 거니깐 bfs 돌려서 트리 하나로 이뤄졌는지 확인하면 될 것 같다. 

 

이까지 구상은 했고 구현은 내일 해야겠다. 

 

 

---

 

처음 생각한 코드

 

부모 노드가 하나인지 확인하고 루트 노드가  하나인지 확인했다. 

 

부모 노드가 하나인지 확인하고 -> 이게 "루트 노드를 제외한 노드는 단 하나의 들어오는 간선이 존재한다." 조건을 확인하는 부분

 

루트 노드가  하나인지 확인했다. -> "들어오는 간선이 하나도 없는 단 하나의 노드가 존재한다."

 

이것 두 개만 확인하고 제출했더니 틀렸다ㅋㅋ

 

3. 루트에서 다른 노드로 가는 경로는 반드시 가능하며, 유일하다. 

 

이 조건을 만족하지 않은 것 같다. 

 

6 8 5 3 5 2 6 4 5 6 0 0 이 테케에서 11 10 10 11을 추가하니 트리라고 판단했다. 

 

bfs를 map으로 써야할 것 같아서 구현 안 했는데 만들어야 할 듯.. 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstring>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    int u, v;
    int count = 1;
    bool is_tree = true;
    
    map<int, vector<int>> child;
    map<int, vector<int>> parent;
    map<int, int> calc;
    
    while (cin >> u >> v)
    {
        if (u < 0 && v < 0)
        {
            return 0;
        }
        
        if (u == 0 && v == 0)
        {
            
            for (auto &pi : parent)
            {
                if (pi.second.size() > 1)
                {
                    is_tree = false;
                }
                    
                calc[pi.first] = 0;
            }
            
            int tmp = 0;
            for (auto &ci : calc)
            {
                if (ci.yy != 0)
                    tmp++;
            }
            
            if (tmp != 1)
                is_tree = false;
            
            if (is_tree)
                printf("Case %d is a tree.\n", count++);
            else
                printf("Case %d is not a tree.\n", count++);
            
            // 초기화
            is_tree = true;
            child.clear();
            parent.clear();
            calc.clear();
            
            continue ;
        }
        
        child[u].push_back(v);
        parent[v].push_back(u);
        calc[u] = 1;
    }
    
    
    return 0;
}

 

 

 

---

 

으으음 bfs 돌려서 도달하지 못하는 부분이 있다면 트리가 아니게 설정했는데 틀렸다. 

 

왜지???

 

왜지??????

 

그리고 본인이 짰지만 코드가 더러운 걸 느낀다. 으악

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstring>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

void clear( std::queue<int> &q )
{
   std::queue<int> empty;
   std::swap( q, empty );
}

int main() {
    int u, v;
    int count = 1;
    bool is_tree = true;
    
    map<int, vector<int>> child;
    map<int, vector<int>> parent;
    map<int, int> calc;
    
    map<int, bool> visited;
    queue<int> Q;
    
    while (cin >> u >> v)
    {
        if (u < 0 && v < 0)
        {
            return 0;
        }
        
        if (u == 0 && v == 0)
        {  
            for (auto &pi : parent)
            {
                if (pi.second.size() > 1)
                {
                    is_tree = false;
                }
                    
                calc[pi.first] = 0;
            }
            
            int tmp = 0;
            int idx;
            for (auto &ci : calc)
            {
                if (ci.yy != 0)
                {
                    tmp++;
                    idx = ci.xx;
                }
            }
            
            if (tmp != 1)
            {
                is_tree = false;
            }
            
            //bfs
            Q.push(idx);
            visited[idx] = true;
            
            while (!Q.empty())
            {
                int curr = Q.front();
                Q.pop();
                
                for (int next : child[curr])
                {
                    if (!visited[next])
                    {
                        visited[next] = true;
                        Q.push(next);
                    }
                }
            }
            
            for (auto &pi : visited)
            {
                if (!pi.yy)
                    is_tree = false;
            }
            
            if (is_tree)
                printf("Case %d is a tree.\n", count++);
            else
                printf("Case %d is not a tree.\n", count++);
            
            // 초기화
            is_tree = true;
            child.clear();
            parent.clear();
            calc.clear();
            clear(Q);
            visited.clear();
            
            continue ;
        }

        visited[u] = false;
        visited[v] = false;
        child[u].push_back(v);
        parent[v].push_back(u);
        calc[u] = 1;
    }
    
    
    return 0;
}

 

아 이걸 빼먹은 듯

 

으악! 맞았다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstring>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

void clear( std::queue<int> &q )
{
   std::queue<int> empty;
   std::swap( q, empty );
}

int main() {
    int u, v;
    int count = 1;
    bool is_tree = true;
    
    map<int, vector<int>> child;
    map<int, vector<int>> parent;
    map<int, int> calc;
    
    map<int, bool> visited;
    queue<int> Q;
    
    while (cin >> u >> v)
    {
        if (u < 0 && v < 0)
        {
            return 0;
        }
        
        if (u == 0 && v == 0)
        {
            if (visited.size() == 0)
            {
                printf("Case %d is a tree.\n", count++);
                continue ;
            }
            
            for (auto &pi : parent)
            {
                if (pi.second.size() > 1)
                    is_tree = false;
                    
                calc[pi.first] = 0;
            }
            
            int tmp = 0;
            int idx;
            for (auto &ci : calc)
            {
                if (ci.yy != 0)
                {
                    tmp++;
                    idx = ci.xx;
                }
            }
            
            if (tmp != 1)
            {
                is_tree = false;
            }
            
            //bfs
            Q.push(idx);
            visited[idx] = true;
            
            while (!Q.empty())
            {
                int curr = Q.front();
                Q.pop();
                for (int next : child[curr])
                {
                    if (!visited[next])
                    {
                        visited[next] = true;
                        Q.push(next);
                    }
                }
            }
            
            for (auto &pi : visited)
            {
                if (!pi.yy)
                    is_tree = false;
            }
            
            if (is_tree)
                printf("Case %d is a tree.\n", count++);
            else
                printf("Case %d is not a tree.\n", count++);
            
            // 초기화
            is_tree = true;
            child.clear();
            parent.clear();
            calc.clear();
            clear(Q);
            visited.clear();
            
            continue ;
        }
        
        visited[u] = false;
        visited[v] = false;
        child[u].push_back(v);
        parent[v].push_back(u);
        calc[u] = 1;
    }
    
    
    return 0;
}

 

이번 문제는 어렵지는 않았는데 구현이 조금 힘들었다. map을 많이 써봐서 다행임