[LeetCode] 802. Find Eventual Safe States 找到最终的安全状态

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 802. Find Eventual Safe States 找到最终的安全状态,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

In a directed graph, we start at some node and every turn, walk along a directed edge of the graph.  If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.html

Now, say our starting node is eventually safe if and only if we must eventually walk to a terminal node.  More specifically, there exists a natural number K so that for any choice of where to walk, we must have stopped at a terminal node in less than K steps.java

Which nodes are eventually safe?  Return them as an array in sorted order.node

The directed graph has N nodes with labels 0, 1, ..., N-1, where N is the length of graph.  The graph is given in the following form: graph[i] is a list of labels j such that (i, j) is a directed edge of the graph.python

Example:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Here is a diagram of the above graph.

Illustration of graph

Note:安全

  • graph will have length at most 10000.
  • The number of edges in the graph will not exceed 32000.
  • Each graph[i] will be a sorted list of different integers, chosen within the range [0, graph.length - 1].

在一个有向图中,若是从一个节点出发走过不少步以后到达了终点(出度为0的节点,无路可走了),则认为这个节点是最终安全的节点。若是根本停不下来,那就是在一个环上,就是不安全节点。要在天然数K步内中止,到达安全节点,返回知足要求的排序好的全部安全节点的索引值。实质是在一个有向图中找出不在环路上的节点。app

解法:DFS,可采用染色的方法对节点进行分类:0表示该结点尚未被访问;1表示已经被访问过了,而且发现是safe的;2表示被访问过了,但发现是unsafe的。咱们采用DFS的方法进行遍历,并返回该结点是不是safe的:若是发现它已经被访问过了,则直接返回是不是safe的标记;不然就首先将其标记为unsafe的,而后进行DFS搜索(此时该结点会处在DFS的路径上,因此后面的DFS一旦到了该结点,就会被认为是造成了环,因此直接返回false)。当整个DFS的搜索都已经结束,而且都没有发现该结点处在环上时,说明该结点是safe的,因此此时将其最终标记为safe便可。空间复杂度是O(n),时间复杂度是O(n)less

解法2: 迭代,记录下每一个节点的出度,若是出度为0那必然是环路外的节点,而后将该点以及指向该点的边删除,继续寻找出度为0的点oop

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> res = new ArrayList<>();
        if(graph == null || graph.length == 0)  return res;
        
        int nodeCount = graph.length;
        int[] color = new int[nodeCount];
        
        for(int i = 0;i < nodeCount;i++){
            if(dfs(graph, i, color))    res.add(i);
        }
        
        return res;
    }
    public boolean dfs(int[][] graph, int start, int[] color){
        if(color[start] != 0)   return color[start] == 1;
        
        color[start] = 2;
        for(int newNode : graph[start]){
            if(!dfs(graph, newNode, color))    return false;
        }
        color[start] = 1;
        
        return true;
    }
}

Python:post

def eventualSafeNodes(self, graph):
    """
    :type graph: List[List[int]]
    :rtype: List[int]
    """
    n = len(graph)
    out_degree = collections.defaultdict(int)
    in_nodes = collections.defaultdict(list) 
    queue = []
    ret = []
    for i in range(n):
        out_degree[i] = len(graph[i])
        if out_degree[i]==0:
            queue.append(i)
        for j in graph[i]:
            in_nodes[j].append(i)  
    while queue:
        term_node = queue.pop(0)
        ret.append(term_node)
        for in_node in in_nodes[term_node]:
            out_degree[in_node] -= 1
            if out_degree[in_node]==0:
                queue.append(in_node)
    return sorted(ret)

Python:url

# Time:  O(|V| + |E|)
# Space: O(|V|)
import collections

class Solution(object):
    def eventualSafeNodes(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[int]
        """
        WHITE, GRAY, BLACK = 0, 1, 2

        def dfs(graph, node, lookup):
            if lookup[node] != WHITE:
                return lookup[node] == BLACK
            lookup[node] = GRAY
            for child in graph[node]:
                if lookup[child] == BLACK:
                    continue
                if lookup[child] == GRAY or \
                   not dfs(graph, child, lookup):
                    return False
            lookup[node] = BLACK
            return True

        lookup = collections.defaultdict(int)
        return filter(lambda node: dfs(graph, node, lookup), xrange(len(graph)))

Python:

class Solution(object):
    def eventualSafeNodes(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[int]
        """
        if not graph: return []

        n = len(graph)
        # 用字段存储每一个节点的父节点
        d = {u:[] for u in range(n)}
        degree = [0] * n
        for u in range(n):
            for v in graph[u]:
                d[v].append(u)
            degree[u] = len(graph[u])

        Q = [u for u in range(n) if degree[u]==0]
        res = []
        while Q:
            node = Q.pop()
            res.append(node)
            for nodes in d[node]:
                degree[nodes] -= 1
                if degree[nodes] == 0:
                    Q.append(nodes)
        return sorted(res) 

C++:

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        vector<int> res;
        if (graph.size() == 0) {
            return res;
        }
        int size = graph.size();
        vector<int> color(size, 0);         // 0: not visited; 1: safe; 2: unsafe.
        for (int i = 0; i < size; ++i) {
            if (dfs(graph, i, color)) {     // the i-th node is safe
                res.push_back(i);
            }
        }
        return res;
    }
private:
    bool dfs(vector<vector<int>> &graph, int start, vector<int> &color) {
        if (color[start] != 0) {
            return color[start] == 1;
        }
        color[start] = 2;       // mark it as unsafe because it is on the path
        for (int next : graph[start]) {
            if (!dfs(graph, next, color)) {
                return false;
            }
        }
        color[start] = 1;       // mark it as safe because no loop is found
        return true;
    }
};

  

 

 

 

All LeetCode Questions List 题目汇总