LeetCode--802. 找到最终的安全状态_leetcode 802

找到最终的安全状态

思路：根据题目描述，从一个节点出发，只要找不到环路，就可以判断该节点为一个安全节点

如何判断是否存在环路呢？
可以采用经典的三色算法
从一点出发，执行DFS搜索，每次经过一个节点，就给该节点染色。若在搜索中到达了某节点发现该节点已经被染色过，则证明存在环路。

1. 当前点未访问过：设置为0（白色）
2. 当前点第一次访：设置为1（灰色）
3. 当前点最终只被访问一次：设置为2（黑色）

安全节点就是黑色节点

/*
4. 找到最终的安全状态
 */

import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.List;

public class Solution802 {
	public List<Integer> eventualSafeNodes(int[][] graph) {
		int length = graph.length;
		int[] state = new int[length];
		List<Integer> res = new ArrayList<>();

		for (int i = 0; i < length; i++) {
			if(dyeing(graph, state, i)){
				res.add(i);
			}
		}
		return res;
	}

	public boolean dyeing(int[][] graph, int[] state, int num) {
		if (state[num] > 0) {
			return state[num] == 2;
		}

		state[num] = 1;
		for (int nextNum : graph[num]) {
			if (!dyeing(graph, state, nextNum)) {
				return false;
			}
		}

		state[num] = 2;
		return true;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39