6416 백준 트리인가?

 

트리인지 아닌지 확인하는 문제이다.

 

노드의 개수가 0개는 트리이므로 간선의 개수가 0이면 트리,

만약 노드의개수가 1이상이면 모든 노드는 root노드를 제외한 간선을 하나씩만 가지고있다.

만약 두개이상 갖게된다면 트리가 아니다.

 

이것을 중점을 문제를 풀었다.

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <memory.h>
#include <map>
using namespace std;
vector<int> node[100001];


int N, M;
int main()
{
    int i = 1;
    for (;;)
    {
        bool treecheck = true;
        map<int, int> tree;
        for (;;)
        {
            cin >> N >> M;

            if ((N == 0 && M == 0) || (N < 0 && M < 0))
            {
                break;
            }
            //트리만들기

            if (tree[N] == NULL)
                tree[N] = 0;
            if (tree[M] == NULL)
                tree[M] = 0;
			
            //만약 1-1로 연결되있다고 한다면 이미 트리가 아니다.
            if (N == M)
            {
                treecheck = false;
            }
            //간선 더해주기
            else
            {
                tree[M]++;
            }

        }
		//음수로 입력받았으면 나가기
        if (N < 0 && M < 0)
            break;
            
        //모든 간선 체크
        int cnt = 0;
        for (auto treea : tree)
        {
            if (treea.second == 0 || treea.second > 1)
                cnt++;
        }

		//만약 간선이 하나도 없으면 트리
        if (tree.size()==0)
        {
            cout << "Case " << i << " is a tree." << '\n';
        }
        //루트하나있고, 1-1같은 간선입력을 안받았다면 트리
        else if (treecheck && cnt==1)
        {
            cout << "Case " << i << " is a tree." << '\n';
        }
        //그외에는 트리가 아니다.
        else
        {
            cout << "Case " << i << " is not a tree." << '\n';
        }
        i++;

    }
}