Determining whether there are rings in a directed graph by topological sorting

The engineering significance of topological sorting

Topological sorting is to construct a topological sequence of a directed graph , Solve the problem of whether the project can proceed smoothly . Structure sometimes $2$ Seed result ：

1. All vertices of this graph are output ： There is no in the drawing 「 Ring 」 There is , yes AOV network （ Directed acyclic graph ）
2. Not all vertices are output ： The illustration shows 「 Ring 」 There is , No AOV network

The main idea

Traverse all penetration degrees to $0$ The node of , And the node refreshes the degree it points to the node , That is, the degree of penetration it points to the node is reduced $1$, When the penetration of this node is $0$, Add it to the queue . Finally, check whether the penetration of all nodes is $0$, If it's all $0$, It shows that the network is a directed acyclic graph .

Example

LeetCode.207 The curriculum

You must take this semester $numCourses$ Courses , Write it down as $0$ To $numCourses-1$ .
Before you take some courses, you need some prerequisite courses . Prerequisite courses by array $prerequisites$ give , among $prerequisites[i]=[a_i,b_i]$, If you want to learn a course $a_i$ You must study the course first $b_i$. for example , The prerequisite course is right for $[0,1]$ Express ： Want to learn the course $0$, You need to finish the course first $1$ .
Please judge whether it is possible to complete all the courses ？ If possible , return $true$; otherwise , return $false$.
Tips ：
$1<=numCourses<=10^5$
$0<=prerequisites.length<=5000$
$prerequisites[i].length==2$
$0<=a_i,b_i<numCourses$
$prerequisites[i]$ All course pairs in are different from each other

Ideas

Use topological sorting to solve problems , When a directed graph is constructed without rings , Then it means that you can complete all courses . The prerequisite course array is equivalent to the edge of a digraph , When the course does not need to take the course first, you can learn , Then the degree of this course is $0$, Otherwise, entering degree is the number of courses that need to be taken first .

Code

class Solution {
    
    public boolean canFinish(int n, int[][] edges) {
    
        int[] d = new int[n];
        List<Integer>[] g = new List[n];
        for(int i = 0; i < n; i++) {
    
            g[i] = new ArrayList<>();
        }
        for(int[] x : edges) {
    
            int a = x[0], b = x[1];
            g[b].add(a);
            d[a]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < n; i++) {
    
            if(d[i] == 0) {
    
                q.offer(i);
            }
        }
        int cnt = 0;
        while(q.size() > 0) {
    
            int x = q.poll();
            cnt++;
            for(int y : g[x]) {
    
                d[y]--;
                if(d[y] == 0) {
    
                    q.offer(y);
                }
            }
        }
        return cnt == n;
    }
}