find-eventual-safe-states

題目連結：find-eventual-safe-states

題目描述

在有向圖中, 我們從某個節點和每個轉向處開始, 沿着圖的有向邊走。 如果我們到達的節點是終點 (即它沒有連出的有向邊), 我們停止。現在, 如果我們最後能走到終點，那麼我們的起始節點是最終安全的。 更具體地說, 存在一個自然數 K, 無論選擇從哪裡開始行走, 我們走了不到 K 步後必能停止在一個終點。哪些節點最終是安全的？ 結果傳回一個有序的數組。該有向圖有 N 個節點，标簽為 0, 1, …, N-1, 其中 N 是 graph 的節點數. 圖以以下的形式給出: graph[i] 是節點 j 的一個清單，滿足 (i, j) 是圖的一條有向邊。

題目分析

題目意思即找出非閉環的所有節點

1. 我們可以從終點開始，即先找出那些沒有出去的邊的節點，即出度為0，這些節點一定符合條件，然後，反向搜尋，找出他的上遊，如果他的上遊的所有出去的邊都是在這些節點當中，則他的上遊節點也是安全的。
2. 我們還可以采用深搜的方式，對每個節點的所有出去的邊進行搜尋，如果他的所有下遊節點都是安全的，則他也是安全的。

算法

反向邊（Graph)

代碼

class Solution {
    
    public List<Integer> eventualSafeNodes(int[][] G) {
        List<Set<Integer>> graph = new ArrayList<>();       // 正向邊圖
        List<Set<Integer>> rgraph = new ArrayList<>();      // 反向邊圖
        Queue<Integer> queue = new LinkedList<>();          // 安全節點隊列
        List<Integer> result = new ArrayList<>();           // 傳回結果集
        boolean[] safe = new boolean[G.length];             // 标記安全節點（因為傳回結果要有序的，這裡用空間換時間）
        
        // 圖的初始化
        for (int i = 0; i < G.length; i++) {
            graph.add(new HashSet<Integer>());
            rgraph.add(new HashSet<Integer>());
        }
        for (int i = 0; i < G.length; i++) {
            for (int j : G[i]) {
                graph.get(i).add(j);
                rgraph.get(j).add(i);
            }
            if (G[i].length == 0) queue.offer(i);
        }

        while (!queue.isEmpty()) {
            // 安全節點集非空，出隊并标記
            int i = queue.poll();
            safe[i] = true;
            for (int j : rgraph.get(i)) {
                // 移除上遊節點到安全節點的邊，如果上遊節點的所有邊都是到安全節點（即graph.get(j).isEmpty()），則入隊
                graph.get(j).remove(i);
                if (graph.get(j).isEmpty()) queue.offer(j);
            }
        }
        // 讀取标記，傳回結果
        for (int i = 0; i < G.length; i++) {
            if (safe[i]) result.add(i);
        }
        return result;
    }
}
           

深度優先搜尋（Depth-first-Search）

代碼

import java.util.*;

class Solution {
    // white表示未搜尋，
    // black表示安全節點，
    // grey表示搜尋中的節點或不安全節點
    enum Color {
        WHITE,
        BLACK,
        GREY,
    }
    
    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> result = new ArrayList<>();
        if (graph.length == 0) return result;
        Color[] color = new Color[graph.length];
        Arrays.fill(color, Color.WHITE);
        for (int i = 0; i < graph.length; i++) {
            if (dfs(graph, i, color)) result.add(i);
        }
        return result;
    }
    
    public boolean dfs(int[][] graph, int i, Color[] color) {
        if (color[i] != Color.WHITE) return color[i] == Color.BLACK;        // 節點i被搜尋過，剪支，快速傳回
        color[i] = Color.GREY;          // 标記節點i在搜尋中
        for (int child : graph[i]) {
            if (!dfs(graph, child, color)) return false;       
        }
        color[i] = Color.BLACK;         // 标記節點i安全
        return true;
    }
}