洞窟探検

プログラマー-洞窟探検

import java.util.*;
class Solution {
    public boolean solution(int n, int[][] path, int[][] order) {
       boolean[] visit = new boolean[n];
	ArrayList<Integer>[] list = new ArrayList[n];
	int [] before = new int[n];
	int [] next = new int [n];
	for (int i = 0; i < n; i++) {
		list[i] = new ArrayList<Integer>();
	}
	for (int i = 0; i < path.length; i++) {
		int [] arr = path[i];
		list[arr[0]].add(arr[1]);
		list[arr[1]].add(arr[0]);
	}
	for(int [] i : order) {
		before[i[1]] = i[0];
	}
        if(before[0] != 0) return false; // 테스트 케이스 30번
	visit[0] = true;
	Stack <Integer> st = new Stack<Integer>();
	for(int i : list[0]) {
		st.add(i);
	}
	while(!st.isEmpty()) {
		int num = st.pop();
		if(visit[num]) continue;
		if(!visit[before[num]]) {
			next[before[num]] = num;
			continue;
		}
		visit[num] = true;
		for(int i : list[num]) {
			if(!visit[i]) st.add(i);
		}
		if(next[num] != 0) st.add(next[num]);
	}
    for(int i = 0; i < n; i++){
    	if(!visit[i]) return false;   
       }
      return true;
    }
}