indegrees in topological sort to solve CouseSchedule with Kahn's algorithm

Question

I am learning to solve a topological sort problem in leetcode

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:
Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.
Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

You may assume that there are no duplicate edges in the input prerequisites.

I read the following toposort solution in discussion area

class Solution5:
    def canFinish(self,numCourses, prerequirements):
    """
    :type numCourse: int
    :type prerequirements: List[List[int]]
    :rtype:bool
    """
    if not prerequirements: return True 
    count = []

    in_degrees = defaultdict(int)
    graph = defaultdict(list)

    for u, v in prerequirements:
        graph[v].append(u)
        in_degrees[u] += 1 #Confused here

    queue = [u for u in graph if in_degrees[u]==0]

    while queue:
        s = queue.pop()
        count.append(s)
        for v in graph(s):
            in_degrees[v] -= 1
            if in_degrees[v] ==0:
                queue.append(v)
    #check there exist a circle
    for u in in_degrees:
        if in_degrees[u]:
            return False 
    return True

I am confused about in_degrees[u] += 1

for u, v in prerequirements:
    graph[v].append(u)
    in_degrees[u] += 1 #Confused here

for directed edge (u,v) , u -----> v , node u has one outdegree while node v has one indegree.

So I think, in_degrees[u] += 1 should be changed to in_degrees[v] += 1 because if there exist (u,v), then v has at least one incoming incident and one indegree

In Degree: This is applicable only for directed graph. This represents the number of edges incoming to a vertex.

However, the orginal solution works.

What's the problem with my understanding?

moonGoose moonGoose · Accepted Answer · 2019-04-02T12:08:03

Look at the line above; graph[v].append(u). The edges are actually going in reverse direction to your assumption and the input format. This is because for topological sort, we want the things with no dependencies/incoming edges to end up at the front of the resulting order, so we direct the edges according to the interpretation, "is a requirement for" rather than "requires". Eg. input pair (0,1) means 0 requires 1, so in the graph we draw a directed edge (1,0) so that 1 can precede 0 in our sort. Thus 0 gains indegree from considering this pair.

indegrees in topological sort to solve CouseSchedule with Kahn's algorithm

1 Answers