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

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

6416번: 트리인가?

1. 주의할 점

- 매 TC마다 Case를 1씩 증가시킨다

- 매 TC마다 벡터와 배열들을 초기화한다

- Root가 2개 이상 있는지, 없는지, 부모가 2개 이상인지, Root에서 모든 Node까지 도달 가능하지 전부 확인한다

- 0 0 또한 빈 트리로, 트리라고 출력해야 한다

 

2. 구현

- 입력받는 모든 Node들을 Set에 넣으며, 간선의 정보는 V[부모]에 자식에 대한 정보를 넣고, Conn[자식]++을 한다

- 마지막 입력으로 0 0 을 받았다면, Test() 함수를 수행하며 Root가 2개 이상 있는지, 없는지, 부모가 2개 이상인지 확인한다

- 위의 조건에서 위배되지 않았다면 Dfs(Root)를 수행하여 모든 Node들에 도달할 수 있는지 확인한다

 

#include <iostream>
#include <set>
#include <vector>
#include <queue>
using namespace std;
set<int> s;
vector<int> v[100001];
int conn[100001], visit[100001];
bool avail;
int root;

void dfs(int val) {
	for (int i = 0; i < v[val].size(); i++) {
		int next = v[val][i];
		if (visit[next] > 0 || next == root) {
			avail = false;
			break;
		}
		visit[next] = 1;
		dfs(next);
	}
}

void test() {
	for (auto it = s.begin(); it != s.end(); it++) {
		int val = conn[*it];
		if (val == 0) {		//root인 경우
			if (root == -1) root = *it;
			else {					//root가 2개 이상인 경우
				avail = false;
				break;
			}
		}
		else if (val > 1) {		//자식이며, 2가지 이상의 부모를 둔 경우
			avail = false;
			break;
		}
	}
	if (root == -1) avail = false;		//root가 없는 경우
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int t = 0, st, e;
	while (1) {
		t++;
		cin >> st >> e;
		if (st == -1 && e == -1) break;
		else if (st == 0 && e == 0) {
			cout << "Case " << t << " is a tree.\n";
			continue;
		}
		//초기화
		for (auto it = s.begin(); it != s.end(); it++) {
			v[*it].clear();
			conn[*it] = 0;
			visit[*it] = 0;
		}
		s.clear();
		avail = true;
		root = -1;

		s.insert(e);
		s.insert(st);
		v[st].push_back(e);
		conn[e]++;
		while (1) {
			cin >> st >> e;
			if (st == 0 && e == 0) break;
			s.insert(st);
			s.insert(e);
			v[st].push_back(e);
			conn[e]++;
		}
		test();
		if (avail) {
			dfs(root);
			for (auto it = s.begin(); it != s.end(); it++) {
				if (*it == root) continue;
				if (visit[*it] > 1) {
					avail = false;
					break;
				}
			}
		}
		if (avail)
			cout << "Case " << t << " is a tree.\n";
		else
			cout << "Case " << t << " is not a tree.\n";
	}
	return 0;
}