[백준OJ] 6416번 트리인가?

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

6416번: 트리인가?

---

 

풀이

1. 입력을 받으며 트리를 만들고, 각 정점마다 진입차수를 구해준다. 또 각 정점이 1,2,3,4 처럼 순서대로 나온다는 보장이 없으므로, set을 이용하여 현재까지 나온 정점들을 기록해준다.

 

2. 만약 처음부터 0 0 이 입력이 됐다면, 트리이다.

 

3. 2번이 아니라면, 진입차수를 이용하여 트리인지 판별을 해준다. 존재하는 모든 노드들의 진입차수를 탐색하며, 진입차수가 0인것의 개수를 구해주며 root를 갱신해준다. 만약 진입차수가 1보다 큰 정점이 나오거나, 진입차수가 0인 정점이 없다면 트리가 아니다.

 

4. 3번에서 루트가 구해졌다면, dfs를 이용해서 사이클이 있는지에 대한 여부와 탐색된 정점들을 기록한다. 그런뒤, 사이클이 있거나 dfs로 방문하지 못한 정점이 있다면, 트리가 아니다.

 

5. 트리인지아닌지 출력해준다.

 

코드

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
#define MAX 100001
using namespace std;

set<int> nodes;
vector<int> tree[MAX];
int indeg[MAX],tc=1;
bool isTree,visited[MAX];

void print_result() {
	cout << "Case " << tc++ << " is " << (isTree ? "a" : "not a") << " tree.\n";
}

void init() {
	for (int node : nodes) tree[node].clear();
	nodes.clear();
	for (int i = 0; i < MAX; i++) {
		indeg[i] = 0;
		visited[i] = false;
	}
	isTree = true;
}

bool make_tree() {
	int u, v;
	cin >> u >> v;
	if (u < 0 && v < 0) {
		return true;
	}

	while (u!=0&&v!=0) {
		tree[u].push_back(v);
		indeg[v]++;
		nodes.insert(u);
		nodes.insert(v);
		
		cin >> u >> v;
	}
	return false;
}

//진입차수가 맞지 않거나, 루트가 없으면 -1리턴, 아니면 루트노드 리턴
int valid_indeg() {
	int zero_cnt = 0;
	int root = -1;
	for (int node : nodes) {
		if (indeg[node] == 0) {
			zero_cnt++;
			root = node;
		}
		else if (indeg[node] > 1) return -1;
	}
	return zero_cnt == 1 ? root : -1;
}

void trace(int root,int node) {
	for (int next : tree[node]) {
		if (visited[next] || next == root) {
			isTree = false;
			return;
		}
		visited[next] = true;
		trace(root, next);
	}
}

void all_visited(int root) {
	for (int node : nodes) {
		if (node == root) continue;
		if (!visited[node]) {
			isTree = false;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	while (true) {
		init();
		bool isEnd = make_tree();
		if (isEnd) break;
		if (nodes.size()) {
			int root = valid_indeg();
			if (root == -1) {
				isTree = false;
			}
			else {
				trace(root, root);
				all_visited(root);
			}
		}
		print_result();
	}

}