802. Find Eventual Safe States

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

Problem

Intuition

• Nhận định: node A là safe node khi 1 trong 2 điều kiện sau xảy ra:
  • node A là terminal node (không có edge nào xuất phát từ node đó - outdegree = 0)
  • “tất cả” các node khác xuất phát từ node A đều là safe node

Approach

• Dùng DFS để tìm các safe node, và dùng color array để đánh dấu từng node:
  • NONE: chưa duyệt qua node này
  • VISITING: đang duyệt node này, tránh trường hợp cyclic (node A –> node B –> … -> node A)
  • NOT_SAFE: not safe node
  • SAFE: safe node
• Để ý, mảng color được dùng xuất phát từ ý tưởng topo sort

Implementation

class Solution {
    private static final int NONE = 0;
    private static final int VISITING = 1;
    private static final int NOT_SAFE = 3;
    private static final int SAFE = 4;
    private int[][] graph;
    private int n;
    private List<Integer> ans;
    private int[] color;

    public List<Integer> eventualSafeNodes(int[][] graph) {
        this.n = graph.length;
        this.graph = graph;
        this.ans = new ArrayList<>();
        this.color = new int[n];

        for (int i = 0; i < n; i++) {
            if (color[i] != NONE) continue;
            dfs(i);
        }

        Collections.sort(ans);
        return ans;
    }

    private int dfs(int i) {
        if (color[i] != NONE) {
            return color[i];
        }

        // avoid cyclic
        color[i] = VISITING;

        // if node is terminal node
        int outDeg = graph[i].length;
        boolean isTerminalNode = outDeg == 0;
        if (isTerminalNode) {
            ans.add(i);
            color[i] = SAFE;
            return SAFE;
        }

        // node is safe node if all neighbors are safe node (or terminal node)
        boolean isSafeNode = true;
        for (int neighbor : graph[i]) {
            int res = color[neighbor] == NONE ? dfs(neighbor) : color[neighbor];
            if (res != SAFE) isSafeNode = false;
        }

        if (isSafeNode) {
            ans.add(i);
            color[i] = SAFE;
            return SAFE;
        } else {
            color[i] = NOT_SAFE;
            return NOT_SAFE;
        }   
    }
}