[Baekjoon Online Judge] 11581 - 구호물자 / Java

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

11581번: 구호물자

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static int[] visited;
	static String answer = "NO CYCLE";
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());

		// visited = 0: 아직 방문하지 않은 상태
		// visited = 1: 탐색 완료된 상태
		// visited = -1: 방문 했지만 탐색 완료되지 않은 상태(탐색 중인 상태)
		visited = new int[N + 1];

		for (int i = 0; i <= N; ++i) {
			graph.add(new ArrayList<Integer>());
		}

		for (int i = 1; i < N; i++) {
			int M = Integer.parseInt(br.readLine());

			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				graph.get(i).add(Integer.parseInt(st.nextToken()));
			}
		}

		findCycle(1);
		System.out.println(answer);
	}

	private static void findCycle(int from) {
		// dfs

		// 현재 정점이 이미 방문된 상태인 경우
		if (visited[from] == -1) {
			// CYCLE 생성됨
			answer = "CYCLE";
			return;
		}

		// 방문 체크
		visited[from] = -1;

		// from에서 갈 수 있는 정점 모두 확인
		for (int v : graph.get(from)) {
			// 탐색 완료된 상태가 아니라면 해당 정점을 시작으로 탐색
			if (visited[v] != 1) {
				findCycle(v);
			}
		}

		// 탐색 완료된 경우
		visited[from] = 1;
	}
}