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

## Topic describes

This is 802 on LeetCode. Find the final security state with medium difficulty.

Tag: “Graph”, “topology Sort”

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.

Example 1:

Input: graph = [[1, 2], [2, 3], [5], [0], [5], [], []] output:,4,5,6 [2] to explain: the diagram above.Copy the code

Example 2:

Input: graph = [[1, 2, 3, 4], [1, 2], [3, 4], [0, 4], []] output: [4]Copy the code

Tip:

• n == graph.length
• 1 <= n <=
$10^4$
• 0 <= graph[i].length <= n
• Graph [I] arrange in strict ascending order.
• The diagram may contain self-loops.
• The number of edges in the figure is in the range [1, 4 * 10410^4104].

## Basic analysis & topological sort

For convenience, let’s make the number of points NNN and the number of edges MMM.

In graph theory, a directed acyclic graph must have at least one topological order corresponding to it, and vice versa.

If you’re not familiar with topological sorting, look at topological sorting.

In simple terms, it is to expand all nodes in the graph into a one-dimensional sequence, for any node in the sequence
$(u, v)$
If in the sequence
$u$

$v$
Before, it indicates that there is a from in the figure
$u$
Set out to achieve
$v$
Pathway, i.e
$u$
In the
$v$
In front of. And vice versa.

At the same time, we need to know the concept of “in” and “out” :

• Input degree: how many edges point directly to the node;
• Outdegree: The number of edges indicated by this node.

Therefore, for the topological ordering of directed graphs, we can output the topological ordering (in BFS mode) with the following ideas:

1. At the beginning, all the nodes whose input degree is 000 are queued (if the input degree is 000, there is no edge pointing to these nodes, and putting them at the top of the topology ordering will not violate the definition of topology ordering).
2. The node is dequeued from the queue, and the dequeued sequence is the topology sequence corresponding to our output. For the currently ejected node XXX, traversal all the ejected degrees of XXX, that is, traversal all the nodes yyy directly pointed to by XXX, and do one subtracting operation for yyy (because XXX node has been ejected from the queue and added to the topological sequence, which is equivalent to being removed from the directed graph from XXX node, The corresponding edge originating from XXX should also be deleted, with the effect that the input degree of the node yyy connected with XXX is reduced by one);
3. After the input degree of YYy is reduced by one, check whether the input degree of YYy is 000. If the input degree of YYy is 000, then yyy is added to the queue (when the input degree of YYy is 000, it means that all nodes in front of YYy in the directed graph are added to the topological order, In this case, YYy can be added as the head of a fragment of the topological order, rather than violating the definition of the topological order);
4. Loop through flow 222, 333 until the queue is empty.

## prove

The premise that the above BFS method can obtain the “topological order of a directed acyclic graph” is that we must be able to find (at least) a “point with an entry degree of 000” and add it to the team at the beginning.

This can be proved by contradiction: assume that the topological order of a directed acyclic graph does not have a point with an indi of 000.

So from any node in the graph
$x$
, and carry out reverse retrieval along the edge, since there is no input degree is
$0$
So each point can find the last node.

When we find a line with length zero
$n + 1$
Since we only have
$n$
Therefore, there must be at least one node recurring in the path, that is, there is a loop in the reverse path, which conflicts with the starting condition of our directed acyclic graph.

It is proved that “topological order of directed acyclic graph” must exist (at least) a “point with entry degree of 000”.

That is, by using the above BFS method, we can iterate through the process until all nodes of the directed acyclic graph are ejected from the queue.

On the other hand, if a graph is not a “directed acyclic graph”, we cannot queue all the nodes, so we can judge whether it is a directed acyclic graph by whether the number of nodes in the queue is NNN.

## Reverse graph + topological sort

Going back to the question, based on the definition of “secure node” in the title, we know that a node is safe if it cannot enter the loop, and is not safe otherwise.

In addition, we found that if we want to judge whether a certain node number XXX is safe, it is not enough to add XXX to the queue at the beginning and run through the topology sorting.

Because we cannot ensure in advance that XXX meets the requirement that the input degree is 000, when we process the node yyy connected with XXX, there may be a case that the input degree of YYy node cannot be reduced to 000, that is, we cannot output the complete part from XXX node to the end in the real topological sequence.

But according to our “proof” section, we can reverse all the edges, and the “in” and “out” are reversed.

For the point set XXX whose “in degree” is 000 in the reverse graph, it is actually the node whose “out degree” is 000 in the original graph. Their “out degree” is 000, and they do not point to any node at all. Therefore, they cannot enter the ring and are safe. At the same time, the nodes pointed by them in the reverse graph (only pointed to their nodes in the original graph) must also be unable to enter the ring. The corresponding nodes in the reverse graph are those whose input degree is 000 after subtracting the input degree corresponding to XXX.

Therefore, the whole process is to reverse the graph and run the topological sort again. If a node appears in the topological sequence, it means that it has entered the queue, indicating that its input degree is 000 and it is safe, while the other nodes are not safe in the ring.

In addition, the way to save the picture here is to use the “chain forward star” which has been used a few days ago. The definition of several arrays and other ways to save the picture, if there are still unfamiliar partners can look up here, this time will not be repeated.

Code:

class Solution {
int N = (int)1e4+10, M = 4 * N;
int idx;
int[] he = new int[N], e = new int[M], 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++;
}
public List<Integer> eventualSafeNodes(int[][] g) {
int n = g.length;
// Save the reverse graph and count the input degree
Arrays.fill(he, -1);
for (int i = 0; i < n; i++) {
for (intj : g[i]) { add(j, i); cnts[i]++; }}// BFS for reverse graph topological sorting
Deque<Integer> d = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
}
while(! d.isEmpty()) {int poll = d.pollFirst();
for (inti = he[poll]; i ! = -1; i = ne[i]) {
int j = e[i];
if (--cnts[j] == 0) d.addLast(j); }}Answer: if a node appears in the topology sequence, it has entered the queue, indicating that its entry degree is 0
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; i++) {
}
returnans; }}Copy the code
• Time complexity: O(n+m)O(n +m)O(n +m)
• Space complexity: O(n+m)O(n +m)O(n +m)

## The last

This is the 802 article in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.

In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.

In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour… .

In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.