題目

https://leetcode.com/problems/find-eventual-safe-states/

題解

用 circle 表示所有環上節點和所有能到達環的節點。

DFS，實際上每一次遍歷都是像遍歷鏈表一樣，判斷鏈表是否有環，如果有環，則將整個鏈放進 circle 中。

有個剪枝優化：如果 DFS 過程中，遇到了 circle 中的元素，則說明之前走過的路徑也應該被放進 circle 中。

最后，返回所有不在 ciecle 中的元素即可。

class Solution {int N;public List<Integer> eventualSafeNodes(int[][] graph) {N = graph.length;Set<Integer> circle = new HashSet<>();Set<Integer> unCircle = new HashSet<>();for (int i = 0; i < N; i++) {HashSet<Integer> seen = new HashSet<>();seen.add(i);dfs(graph, circle, unCircle, seen, i);}List<Integer> result = new ArrayList<>();for (int i = 0; i < N; i++) {if (!circle.contains(i)) result.add(i);}return result;}public void dfs(int[][] graph, Set<Integer> circle, Set<Integer> unCircle, Set<Integer> seen, int i) {if (circle.contains(i)) {circle.addAll(seen);return;}if (unCircle.contains(i)) {return;}for (int j : graph[i]) {if (seen.contains(j)) {circle.addAll(seen);return;} else {seen.add(j);dfs(graph, circle, unCircle, seen, j);seen.remove(j);}}if (!circle.contains(i)) unCircle.addAll(seen);} }

總結

以上是生活随笔為你收集整理的leetcode 802. Find Eventual Safe States | 802. 找到最终的安全状态（有向图DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。