[백준] 6416 트리인가?💫

백준 6416 트리인가?

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

• 33% 틀렸습니다

#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

//트리의 조건 (비어있는 트리 가능)
//1. 루트 노드 한 개 (들어오는 간선 0개) 
//2. 나머지 노드 들어오는 간선 1개 초과 X
//3. 루트에서 출발하여 노드를 방문하는 경로 유일 & 모든 노드 반드시 존재

set<int> node;

//<curnode, curnode에서 나가는 간선>
map<int, vector<int>> out;

//<curnode, curnode로 들어오는 간선의 수>
map<int, int> in;

//<curnode, curnode 방문 여부>
map<int, int> visited;

bool isTree;

void dfs(int curnode) {
	visited[curnode] = 1;

	for (int i = 0; i < out[curnode].size(); ++i) {
		int nextnode = out[curnode][i];

		if (visited[nextnode] == 0)
			dfs(nextnode);

		//nextnode이미 방문했다면, nextnode로 가는 경로 유일하지 않다
		else if(visited[nextnode] > 0)
			isTree = false;
	}
	return;
}

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

	//테스트 케이스 수
	int k = 1;
	while (true) {

		//초기화
		node.clear();
		out.clear();
		in.clear();
		visited.clear();

		//간선 입력 받기
		while (true) {
			int u, v;
			cin >> u >> v;

			if (u < 0 && v < 0)
				exit(0);

			if (u == 0 && v == 0) 
				break;

			//노드 u,v 존재
			node.insert(u);
			node.insert(v);

			//u에서 v로 가는 간선 존재
			out[u].push_back(v);
			in[v]++;
		}

		//비어있는 경우
		if (node.size() == 0) {
			cout << "Case k is a tree.\n";
			continue;
		}

		//비어있지 않은 경우
		isTree = true;

		//1. 루트 노드 한 개인지 확인
		//2. 나머지 노드 들어오는 간선 1개 초과 X 인지 확인
		int root = -1;
		for (auto it = node.begin(); it != node.end(); ++it) {
			int curnode = *it;

			//들어오는 간선 0개라면 루트 노드
			if (in[curnode] == 0) {
				if (root == -1)
					root = curnode;
				//루트 노드 한 개 이상이라면 트리가 아니다
				else {
					isTree = false;
					break;
				}
			}
			//들어오는 간선 1개 초과라면 트리가 아니다
			else if(in[curnode] > 1) {
				isTree = false;
				break;
			}
		}
		//루트 노드가 없다면 트리가 아니다 (싸이클)
		if (root == -1) isTree = false;
		
		for (auto it = node.begin(); it != node.end(); ++it)
			visited[*it] = 0;

		//3-1. 루트에서 출발하여 노드를 방문하는 경로 유일한지 확인
		if (isTree) dfs(root);

		//3-2. DFS 후 방문하지 못한 노드가 있는지 확인
		if (isTree) {
			for (auto it = node.begin(); it != node.end(); ++it) {
				if (visited[*it] == 0) {
					isTree = false;
					break;
				}
			}
		}
		
		if(isTree) cout << "Case k is a tree.\n";
		else cout << "Case k is not a tree.\n";
	
		k++;
	}
	return 0;
}