Solution by Finding Strongly Connected Components (SCC size > 1 => false, all equals 1 => true)


  • 1
    D
    public class Solution {
        private int f; // finishing time
        private int count; // size of strongly connected components
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            //find the strongly connected components
            //if there exists one SCC whose size > 1, then return false, otherwise return true
            this.f = 0;
            int[] ftime = new int[numCourses];
            Integer[] course = new Integer[numCourses];
            HashMap<Integer, Character> m = new HashMap<Integer, Character> ();
            int i;
            for(i = 0; i < numCourses; i ++) {
                m.put(i, 'w');
                course[i] = i;
            }
            for(i = 0; i < numCourses; i ++) {
                if (m.get(i) == 'w') {
                    dfs_visit(i, prerequisites, m, ftime);
                }
            }
            Arrays.sort(course, new Comparator<Integer> () {
                @Override
                public int compare(Integer i1, Integer i2) {
                    if (ftime[i1] == ftime[i2]) return 0;
                    else if(ftime[i1] < ftime[i2]) return -1;
                    else return 1;
                }
            });
            this.f = 0;
            int prev;
            for(i = 0; i < numCourses; i ++) {
                m.put(i, 'w');
            }
            for(i = 0; i < numCourses; i ++) {
                prev = this.f;
                dfs_visit(course[i], prerequisites, m, ftime);
                if (this.f - prev > 1) return false;
                else prev = this.f;
            }
            return true;
        }
        
        public void dfs_visit(int currCourse, int[][] prerequisites, HashMap<Integer, Character> m, int[] ftime) {
            if (m.get(currCourse) == 'w') {
                m.put(currCourse, 'g');
                int l = prerequisites.length;
                for(int i = 0; i < l; i ++) {
                    if(prerequisites[i][0] == currCourse && m.get(prerequisites[i][1]) == 'w') {
                        dfs_visit(prerequisites[i][1], prerequisites, m, ftime);
                    }
                }
            }
            m.put(currCourse, 'b');
            ftime[currCourse] = this.f;
            this.f ++;
            return;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.