[백준]6416 트리인가?

1. 풀이

(1) 입력이 하나의 그래프임이 보장될때 트리일 조건은 (노드개수-1)==(간선개수)가 된다.

(2) 간선개수가 0인것은 빈트리이므로 이것역시 트리이다.

 

2. 소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

int main() {
	int num1, num2;
	string ans;
	int t = 1;
	while (1) {
		cin >> num1 >> num2;
		if (num1 < 0) {
			break;
		}
		// test case
		else {
			vector<pair<int, int>> graph;
			set<int> s;
			// 입력
			while (1) {
				if (num1 == 0 and num2 == 0) {
					break;
				}
				else {
					graph.push_back(make_pair(num1, num2));
					s.insert(num1);
					s.insert(num2);
				}
				cin >> num1 >> num2;
			}
			if (s.size() - 1 == graph.size() or s.size()==0) {
				printf("Case %d is a tree.\n", t);
			}
			else {
				printf("Case %d is not a tree.\n", t);
			}
		}
		t++;
	}

	return 0;
}