This is the fifth day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Leetcode -802- Find the final security status

[Blog link]

The way to study 🐔

The nuggets home page

[Topic description]

In a directed graph, starting from a node, each step travels along a directed edge in the graph. If the reached node is the end point (that is, it has no directed edge), then stop.

For a starting node, if starting from the node, no matter which direction is chosen for each step, the end point must be reached in finite steps, then the starting node is said to be safe.

Return an array of all the safe starting nodes in the graph as the answer. The elements in the answer array should be arranged in ascending order.

The directed graph has n nodes, numbered from 0 to N-1, where n is the number of nodes of the graph. Graph [I] is a list of nodes numbered j, such that (I, j) is a directed edge of the graph.

Input:Graph = [[1, 2], [2, 3], [5], [0], [5], [], []]Output:,4,5,6 [2]Explanation:The diagram is shown above.

Input:Graph = [[1, 2, 3, 4], [1, 2], [3, 4], [0, 4], []]Output:[4]

[Topic link]

Leetcode title link

[making address]

Code link

[思路介绍]

Idea 1:DFS + violence

• DFS traverses all nodes
• Each DFS node will not traverse the same node, once the same, it is not safe (the current security check is a bit complex, but also want to optimize the idea)
• You can do that by hashing
• The TLE

Set<Integer> set = new HashSet<>();
 public List<Integer> eventualSafeNodes(int[][] graph) {
     int[] arr = new int[graph.length];
     for (int i = 0; i < graph.length; i++) {
         set = new HashSet<>();
         set.add(i);
         arr[i] = dfs(graph, i,set) ? 1 : 0;
     }
     List<Integer> res = new ArrayList<>();
     for (int i = 0; i < arr.length; i++){if (arr[i]>0){ res.add(i); }}return res;
 }

 public boolean dfs(int[][] graph, int i,Set<Integer> set) {
     if (i>= graph.length){
         return false;
     }
     for (int tar: graph[i]
          ) {
         if (set.contains(tar)){
             return false;
         }
         Set<Integer> temp = new HashSet<>();
         temp.addAll(set);
         temp.add(tar);
         boolean flag = dfs(graph,tar,temp);
         if(! flag){return false; }}return true;
 }
Copy the code

$Time complexity O(n^{2})$

Idea 2: Optimize idea 1

• The security node check is optimized by memorization
• Security records the nodes that have been traversed and can safely reach the destination, reducing the number of traversals

Set<Integer> security = new HashSet<>();
        public List<Integer> eventualSafeNodes(int[][] graph) {
            int[] arr = new int[graph.length];
            for (int i = 0; i < graph.length; i++) {
                Set<Integer> set = new HashSet<>();
                set.add(i);
                arr[i] = dfs(graph, i, set) ? 1 : 0;
            }
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] > 0) { res.add(i); }}return res;
        }

        public boolean dfs(int[][] graph, int i, Set<Integer> set) {
            if (i >= graph.length) {
                return false;
            }
            for (int tar : graph[i]
            ) {
                if (security.contains(tar)) {
                    continue;
                }
                if (set.contains(tar)) {
                    return false;
                }
                Set<Integer> temp = new HashSet<>();
                temp.addAll(set);
                temp.add(tar);
                boolean flag = dfs(graph, tar, temp);
                if(! flag) {return false;
                } else{ security.add(tar); }}return true;
        }
Copy the code

$Time complexity O(n^{2})$

Idea 3:Directed graph + reverse graph +BFS+ topological sort

• Interesting new knowledge was added
• The small white is very difficult
• This is the first time in the daily question series that the concept of topological sorting has been introduced
• So let’s talk about how this relates to topological sorting
• According to the passage, the result of the passage is as follows
  • All nodes in the sequence are guaranteed to have no loop in the directed path
• One of the properties of topological sorting is also simple:
• If there is a directed path u-> V for two nodes (u,v), then v must not have a directed path to U (acyclic).
• To be able to getTopological order of a directed acyclic graphThe premise is:
  • We must be able to find (at least) a “point of zero entry” to start with.
• The property just coincides with the meaning of the question
• And then I’m going to give you two definitions
  • Degree of entry: the number of edges that can reach this node
  • Out-degree: the number of edges starting from this node
• In this case, we can now put all the nodes with an input degree of 0 and no way to reach this node into the result set
• Putting these nodes in the head of the topological sort does not affect the definition of the topological sequence
• For the currently popped node X, iterate over all outdegrees of X
• I’m going to iterate over all the nodes y that are directly pointed to by x
• Do to yThe degree of minus oneoperation
  • Because the X node has been ejected from the queue and added to the topology order
  • This is equivalent to removing the x node from the directed graph
  • The corresponding edges originating from x should also be deleted
  • The effect is that the input degree of the node y connected to x is reduced by one
• The yThe degree of minus oneafter
  • Check that the input of y is zero
  • If it’s 0 then you put y on the team
  • When the input of y is 0
  • All nodes before y in the directed graph are added to the topology sequence
  • In this case, y can be added as the header of a fragment in the topology order
  • Without violating the definition of topological order
• In this case, you want to determine whether the number of nodes x is safe
• It is not enough to start by joining x and running through the topology
  • Because the input does not confirm that the node input degree is zero, it is not possible to add the node directly to the topology sequence
• This sentence can also be interpreted as when the indeterminateness of the x node is 0
• The input degree of y node may not be reduced to 0 according to the above operation
• So you can construct an inverse graph based on what you did before, where you invert all the edges
  • If the entry degree is 0, it corresponds to the point in the original drawing where the exit degree is 0
  • The degree of the original image is 0, which means that the change point is the security node
  • And all the edges pointing to this node can also represent security
• So the whole process is to reverse the graph
• Run through topological sorting
• If a node appears in a topological sequence
• Indicates that the device has been queued
• Indicating that its entry degree is 0 (corresponding to the original image exit degree is 0)
• It’s safe
• The remaining nodes are non-secure nodes in the ring.
• Chain building diagram (specific can refer to the explanation of the public number of the three leaf tycoon before)

int N = (int)1e4+10, M = 4 * N, idx = 0;
int[] e = new int[M], he = new int[N], ne = new int[M];
int[] cnts = new int[N];
void add(int a, int b){
    e[idx] = b;
    ne[idx] = he[a];
    he[a] = idx;
    idx++;
}
public List<Integer> eventualSafeNodes(int[][] graph) {
    // Initialize the graph
    Arrays.fill(he,-1);
    int n = graph.length;
    // Construct the reverse diagram
    for (int i = 0; i < n; i++) {
        for (int num: graph[i]
             ) {
            // Reverse build
            add(num,i);
            // The input of the reverse graph (the output of the original graph)cnts[i]++; }}//BFS for topological sort
    Deque<Integer> dq = new ArrayDeque<>();
    // Add all nodes whose inverse graph input degree is 0 to the topology sequence
    for (int i = 0 ; i < cnts.length; i++){
        // If the entry degree is 0, join the BFS queue
        if (cnts[i] == 0)dq.add(i);
    }
    while(! dq.isEmpty()){int temp = dq.poll();
        for (inti = he[temp]; i ! = -1 ; i = ne[i]) {
            int j= e[i];
            Subtracting the current entry degree to 0 can continue to join the BFS queue
            if (--cnts[j]==0)dq.addLast(j);
        }
    }
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (cnts[i] == 0) ans.add(i);
    }
    return ans;
}
Copy the code

• Time complexity: O(n + m)