Two Ways :
- BFS
- DFS (3 state visited ) 如果要得到最终的结果 需要每次在链表头部插入
207. Course Schedule
We can see the course that have a pre course as two nodes in a graph with an arrow between
each other. Thus the question is can we find a path that walk through the nodes in the graph that consisting
of all the courses. We need to perform Topological Sorting and count the number of nodes encounter during
the process
BFS
/** TP sort**/
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int indegree[] = new int[numCourses];
// Convert graph presentation from edges to indegree of adjacent list.
List<List<Integer>> graph = new ArrayList();
for(int i = 0;i < numCourses;i++){
graph.add(new ArrayList<Integer>());
}
//Indegree - how many prerequisites are needed.
for (int i = 0; i < prerequisites.length; i++)
{
indegree[prerequisites[i][1]]++;
graph.get(prerequisites[i][0]).add(prerequisites[i][1]);
}
Queue<Integer> q = new LinkedList<Integer>();
for (int i = 0; i < numCourses; i++){
if(indegree[i] == 0){
q.offer(i);
}
}
int count = q.size();
while (!q.isEmpty()) {
int pre = q.poll();
for(Integer i:graph.get(pre)){
indegree[i]--;
if(indegree[i] == 0) {
count++;
q.offer(i);
}
}
}
return (count == numCourses);
}
}
DFS
An alternative algorithm for topological sorting is based on depth-first search. The algorithm loops
through each node of the graph, in an arbitrary order, initiating a depth-first search that terminates
when it hits any node that has already been visited since the beginning of the topological sort or the
node has no outgoing edges (i.e. a leaf node):
We can think of the problem as checking whether there is a loop in the graph if there is then return false
DFS from every possible point and mark each node during traversal as temporary visited and mark it as final
visisted in the end if there is a cycle in the process then return false. Otherwise since we visited all the
nodes following the direction thus we can take all the courses
Since each edge and node is visited once, the algorithm runs in linear time O(N)
public class Solution {
//use three state, if marked as 2 means we finished DFS this point
//if during the process we meet a point that are on going visit return false
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList();
for(int i = 0;i < numCourses;i++){
graph.add(new ArrayList<Integer>());
}
for (int i = 0; i < prerequisites.length; i++)
{
graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
}
int[] visited = new int[numCourses];
//start branching from any nodes in the graph
for(int i = 0;i < numCourses;i++){
if(visited[i]!= 2){
if(!helper(i,graph,visited))return false;
}
}
return true;
}
// 1--temp,2--perm,0--unvisited
public boolean helper(int course,List<List<Integer>> graph,int[] visited){
visited[course] = 1;
List<Integer> list = graph.get(course);
for(Integer cur:list){
if(visited[cur] == 1)return false;
else if(visited[cur] == 0){
if(!helper(cur,graph,visited))return false;
}
}
visited[course] = 2;
return true;
}
}
210. Course Schedule II
Same Algorithm just create an array and an index to track. Pay attention to the length of the created array should
be the number of courses
public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] res = new int[numCourses];
List<List<Integer>> map = new ArrayList();
int[] indegree = new int[numCourses];
//construct graph
for(int i = 0;i < numCourses;i++){
map.add(new ArrayList<Integer>());
}
for(int[] arr: prerequisites){
map.get(arr[1]).add(arr[0]);
indegree[arr[0]]++;
}
//find the 0 indegree nodes
Queue<Integer> q = new LinkedList<Integer>();
for(int i = 0;i < numCourses;i++){
if(indegree[i] == 0)q.add(i);
}
int idx = 0;
while(!q.isEmpty()){
int cur = q.poll();
res[idx++] = cur;
for(Integer j : map.get(cur)){
if(--indegree[j] == 0){
q.add(j);
}
}
}
if(idx == numCourses)return res;
return new int[0];
}
}
Add to List
444. Sequence Reconstruction
Check whether there is one and only topological sort sequence: 每一个岔路口只能有一种选择 也就是说BFS里面的Queue里面只能时刻保持一个元素
最后还要检查idx是否走完了所有点 因为有可能TP Sort的结果是前面Prefix
Also Pay attention to duplicate edges!
时间复杂度 O(N)
/** Prove that there exist one and only tp sequence and the sequence equal to the given sequence! **/
public class Solution {
public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
//compute the graph
HashMap<Integer,Set<Integer>> graph = new HashMap<Integer,Set<Integer>>();
HashMap<Integer,Integer> indegree = new HashMap<Integer,Integer>();
for(List<Integer> subList : seqs){
int n = subList.size();
init(graph,indegree,subList);
for(int i = 0;i < n - 1;i++){
int first = subList.get(i);
int second = subList.get(i + 1);
Set<Integer> neighbor = graph.get(first);
//avoid duplicate
if(!neighbor.contains(second)){
indegree.put(second,indegree.get(second) + 1);
}
neighbor.add(second);
graph.put(first,neighbor);
}
}
//extract the indegree 0 node
Queue<Integer> q = new LinkedList<Integer>();
for(Map.Entry<Integer, Integer> entry: indegree.entrySet()) {
if(entry.getValue() == 0) q.offer(entry.getKey());
}
int idx = 0;
while(!q.isEmpty()){
//one and only path for each sub route
if(q.size() != 1)return false;
Integer cur = q.poll();
if(idx == org.length || cur != org[idx++]) return false;
for(Integer adj: graph.get(cur)){
int id = indegree.get(adj);
indegree.put(adj,id - 1);
if(id == 1)q.offer(adj);
}
}
//tricky need to check whether we walk through
return idx == org.length && idx == graph.size();
}
public void init(HashMap<Integer,Set<Integer>> graph,HashMap<Integer,Integer> indegree,List<Integer> subList){
for(Integer i : subList){
if(!indegree.containsKey(i)){
indegree.put(i,0);
}
if(!graph.containsKey(i)){
graph.put(i,new HashSet<Integer>());
}
}
}
}