210. Course Schedule II

Posted on | Edited on | Views:

https://leetcode.com/problems/course-schedule-ii/

Topological Sorting based on DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
    class graph{
        int capacity;
        ArrayList<ArrayList<Integer>> adj;
        
        graph(int capacity){
            this.capacity=capacity;
            adj=new ArrayList<>(capacity);
            for(int i=0;i<capacity;i++) adj.add(new ArrayList<Integer>());
        }
        void addEdge(int v,int w){
            adj.get(v).add(w);
        }
        void topologicalSortUtil(int i,boolean[] visited,LinkedList<Integer> stack){
            visited[i]=true;
            Iterator<Integer> itr=adj.get(i).iterator();
            while(itr.hasNext()){
                int nextCourse=itr.next().intValue();
                if(!visited[nextCourse]) topologicalSortUtil(nextCourse,visited,stack);
            }
            stack.push(i);
        }
        int[] topologicalSort(){
            LinkedList<Integer> stack=new LinkedList<>();
            boolean[] visited=new boolean[this.capacity];
            
            // check if there is a cycle in the graph
            for(int i=0;i<this.capacity;i++){
                if(!noCycle(i,visited)) return new int[0];
            }
            
            for(int i=0;i<this.capacity;i++){
                if(!visited[i]) topologicalSortUtil(i,visited, stack);
            }
            // stack push elements from leftmost to right
            return stack.stream().mapToInt(i->i).toArray();
        }
        boolean noCycle(int i,boolean[] visited){
            if(visited[i]) return false;
            visited[i]=true;
            Iterator<Integer> itr=adj.get(i).iterator();
            for(int j=0;j<adj.get(i).size();j++){
                if(!noCycle(adj.get(i).get(j),visited)) return false;
            }
            visited[i]=false;
            return true;
        }
    }
        public int[] findOrder(int numCourses, int[][] prerequisites) {
        graph g=new graph(numCourses);
        for(int[] i:prerequisites) g.addEdge(i[1],i[0]);
        return g.topologicalSort();
    }
}

/* Drive method*/
public class MyClass {
    public static void main(String[] args) {
        int numCourses=2;
        int[][] prerequisites={{1,0},{0,1}};
        System.out.println(Arrays.toString(new Solution().findOrder(numCourses, prerequisites)));
    }
}

Topological Sorting based on BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if(prerequisites==null) return new int[0];
        // create graph
        HashMap<Integer,ArrayList<Integer>> graph=new HashMap<>();
        int[] inDegree=new int[numCourses];
        for(int[] edge:prerequisites){
            inDegree[edge[0]]++;
            if(!graph.containsKey(edge[1])){
                ArrayList<Integer> ls=new ArrayList<>();
                ls.add(edge[0]);
                graph.put(edge[1],ls);
            }else{
                graph.get(edge[1]).add(edge[0]);
            }
        }
        // put vertex without incoming edges into queue
        LinkedList<Integer> queue=new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(inDegree[i]==0) queue.offer(i);
        }
        
        // output int[]
        int[] res=new int[numCourses];
        int idx=0;
        while(!queue.isEmpty()){
            int course=queue.poll();
            res[idx++]=course;
            if(graph.get(course)!=null){
                for(int nextCourse:graph.get(course)){
                    inDegree[nextCourse]--;
                    if(inDegree[nextCourse]==0) queue.offer(nextCourse);
                }
            }
        }
        return idx==numCourses?res:new int[0];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
class Solution {
    private boolean noCycle(int course,boolean[] visited,ArrayList<Integer>[] graph){
        if(visited[course]) return false;
        visited[course]=true;
        for(int i=0;i<graph[course].size();i++){
            if(!noCycle(graph[course].get(i),visited,graph)) return false;
        }
        visited[course]=false;
        return true;
    }
    
    private void topologicalSortUtil(int i,LinkedList<Integer> stack,boolean[] visited,ArrayList<Integer>[] graph){
        visited[i]=true;
        Iterator<Integer> itr=graph[i].iterator();
        while(itr.hasNext()){
            int tmp=itr.next().intValue();
            if(!visited[tmp]) topologicalSortUtil(tmp,stack,visited,graph);
        }
        // LinkedList push form leftmost to right
        stack.push(i);
    }
    
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if(prerequisites==null) return new int[0];
        // create graph
        ArrayList<Integer>[] graph=new ArrayList[numCourses];
        for(int i=0;i<numCourses;i++) graph[i]=new ArrayList<Integer>();
        for(int[] edge:prerequisites) graph[edge[1]].add(edge[0]);
        // set visit flags
        boolean[] visited=new boolean[numCourses];
        
        // check cycles
        for(int i=0;i<numCourses;i++){
            if(!noCycle(i,visited,graph)) return new int[0];
        }
        
        // if no cycles, output array
        LinkedList<Integer> stack=new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(!visited[i]) topologicalSortUtil(i,stack,visited,graph);
        }

        return stack.stream().mapToInt(i->i).toArray();
    }
}
*/
0%