[6416번] 트리인가?

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

문제 정의를 읽어보면 다음과 같다.

1. 들어오는 간선이 하나도 없는 단 하나의 노드가 존재한다. 이를 루트(root) 노드라고 부른다.

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

3. 루트에서 다른 노드로 가는 경로는 반드시 가능하며, 유일하다. 이는 루트를 제외한 모든 노드에 성립해야 한다.

이 3가지를 이용하여 문제를 풀어보면 다음과 같다.

1. 루트노드 존재여부 및 루트노드가 유일한지 확인한다.

2. 진입차수가 무조건 1이어야 한다.(루트노드를 제외하고)

3. 엣지 + 1 == 노드 수인지 확인한다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
 
using namespace std;
 
int indegree[10002];
int outdegree[10002];
bool nodeChk[10002];
 
int main()
{
    int tc = 1;
    int edge = 0;
    int maxNode = -1;
    int minNode = 987654321;
    int root = -1;
 
    bool chk = true;
    while (tc)
    {
        int a, b;
        scanf("%d %d", &a, &b);
 
        nodeChk[a] = nodeChk[b] = true;
 
        if (a == -1 && b == -1)
            break;
 
        if(a != 0 && b != 0)
        {
            maxNode = max({ maxNode, a,b });
            minNode = min({ minNode, a,b });
        }
        if (!a && !b)
        {
            // root노드 찾는과정, 이때 루트 2번발견되면 트리 x
            for (int i = minNode; i <= maxNode; i++)
            {
                if (indegree[i] == 0 && outdegree[i] != 0)
                {
                    if (root != -1)
                        chk = false;
                    
                    root = i;
                }
            }
 
            // 트리 정의 :: 진입차수 2개이상되는게 발견되면 트리 x
            for (int i = minNode; i <= maxNode; i++)
                if (indegree[i] >= 2)
                    chk = false;
                
            // 노드 개수 카운트
            int get = 0;
            for (int i = minNode; i <= maxNode; i++)
                if (nodeChk[i])
                    get++;
                
            // 트리 정의 :: 엣지 + 1 == 노드
            if (edge + 1 != get)
                chk = false;
            
            // 트리 정의 :: 루트가 존재해야 한다.
            if (root == -1)
                chk = false;
            
 
            if (chk || !edge)
                printf("Case %d is a tree.\n", tc++);
            else
                printf("Case %d is not a tree.\n", tc++);
 
            memset(indegree, 0, sizeof(indegree));
            memset(outdegree, 0, sizeof(outdegree));
            memset(nodeChk, false, sizeof(nodeChk));
 
            root = -1;
            edge = 0;
            maxNode = -1;
            minNode = 987654321;
            chk = true;
            continue;
        }
 
        indegree[b]++;
        outdegree[a]++;
        edge++;
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>