The problem here is basically detecting a cycle in a directed graph.
There are a few ways of approaching this but the most straightword ways are topological sorting and counting using BFS and checking if a vertex was visited before in DFS.
In BFS-Topological Sort, if we end the loop when there are vertices with in-degree greater than 0, then we didn't the traverse the entire graph. We can keep the number of vertices that we poll and compare at the end.
210. Course Schedule II
Problem: https://leetcode.com/problems/course-schedule-ii/
Here, we need the actual topological sort order of the vertices of a digraph. We can once again apply Kahn's algorithm for this. It's simple as we only add the vertices we poll to a list and return it.
In DFS, topological sorting is achieved by working backwards. If I have a graph like 0->1->2, by the logic of DFS, I am able to process the last vertex first. I should then add this vertex to the end of the list. It all works backward from there.
The algorithms discussed here will come to use in #241.
For this question, it is best to review the algorithms that were used to solve #180 and #190.
207. Course Schedule
Problem: https://leetcode.com/problems/course-schedule/
The problem here is basically detecting a cycle in a directed graph. There are a few ways of approaching this but the most straightword ways are topological sorting and counting using BFS and checking if a vertex was visited before in DFS. In BFS-Topological Sort, if we end the loop when there are vertices with in-degree greater than 0, then we didn't the traverse the entire graph. We can keep the number of vertices that we poll and compare at the end.
210. Course Schedule II
Problem: https://leetcode.com/problems/course-schedule-ii/ Here, we need the actual topological sort order of the vertices of a digraph. We can once again apply Kahn's algorithm for this. It's simple as we only add the vertices we poll to a list and return it. In DFS, topological sorting is achieved by working backwards. If I have a graph like
0->1->2, by the logic of DFS, I am able to process the last vertex first. I should then add this vertex to the end of the list. It all works backward from there.The algorithms discussed here will come to use in #241.