【Java】802. 找到最终的安全状态----学习图论，使用深度遍历，避免入坑！！！_java802

在有向图中，以某个节点为起始节点，从该点出发，每一步沿着图中的一条有向边行走。如果到达的节点是终点（即它没有连出的有向边），则停止。

对于一个起始节点，如果从该节点出发，无论每一步选择沿哪条有向边行走，最后必然在有限步内到达终点，则将该起始节点称作是 安全 的。

返回一个由图中所有安全的起始节点组成的数组作为答案。答案数组中的元素应当按 升序 排列。

该有向图有 n 个节点，按 0 到 n - 1 编号，其中 n 是 graph 的节点数。图以下述形式给出：graph[i] 是编号 j 节点的一个列表，满足 (i, j) 是图的一条有向边。

示例 1：

输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出：[2,4,5,6]
解释：示意图如上。
示例 2：

输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
输出：[4]

提示：

n == graph.length
1 <= n <= 104
0 <= graph[i].length <= n
graph[i] 按严格递增顺序排列。
图中可能包含自环。
图中边的数目在范围 [1, 4 * 104] 内。

代码：
public List<Integer> eventualSafeNodes(int[][] graph) {
		List<Integer> list=new ArrayList<>();
		int len=graph.length;
		int[]count=new int[len];
		for(int i=0;i<len;i++) {
			if(dfs(graph,count,i)) {
				list.add(i);
			}
		}
		return list;
	}
	public boolean dfs(int[][] graph,int []count,int index) {
		if(count[index]>0) {
			return count[index]==2;
		}
		//1表示此节点访问过，不知是不是在回路中
		count[index]=1;
		for (int child :graph[index]) {
			if(count[child]==2) {
				continue;
			}
			if(count[child]==1||!dfs(graph, count,child)) {
				return false;
			}
		}
		//2表示此节点访问过，但未在回路中
		count[index]=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