[백준] 6416-트리인가?(C++)

문제링크:https://www.acmicpc.net/problem/6416

6416번: 트리인가?

 

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

3가지조건을 만족해야합니다.

그리고 수의 범위가 주어지지 않았기 때문에 배열의 크기를 정해놓는 것은 안됩니다.

 

위의 조건들에 대해서 곰곰히 생각하다 보면 집합에 대해서 생각하실 수 있습니다. 

위 조건들을 만족시키위해서 노드 집합의 개수 s + 1 과  입력받은 횟수가 같아야 한다는 것을 알 수있습니다. 

 

 

정답코드입니다.

#include <iostream>
#include <cstring>
#include <vector>
#include <set>
using namespace std;

int a, b;
int u = 0;
set <int> arr;

int main() {
	
	while (1) {
		u++;
		arr.clear();
		int sum = 0;
		bool jud2 = true;
		for (int k = 0;; k++) {
			
			cin >> a >> b;
			if (k == 0) {
				if (a == -1 && b == -1)
					return 0;
				else if (a == 0 && b == 0) {
					cout << "Case " << u << " is a tree." << '\n';
					jud2 = false;
					break;
				}
			}
			if (a == 0 && b == 0)
				break;
			arr.insert(a);
			arr.insert(b);
			sum++;

		}
		if (jud2 == true) {
			if (sum + 1 == arr.size())
				cout << "Case " << u << " is a tree." << '\n';
			else
				cout << "Case " << u << " is not a tree." << '\n';
		}
	}

	return 0;
}