OO easy to read java solution


  • 38
    A
    public class Solution {
        static class Course {
            private boolean vis;
            private boolean done;
            private ArrayList<Course> pre = new ArrayList<Course>();
            
            void addPre(Course preCourse) {
                pre.add(preCourse);
            }
            
            boolean isCyclic() {
                if( done ) {
                    return false;
                }
                if( vis ) {
                    return true;
                }
                vis = true;
                
                for(Course preCourse: pre ) {
                    if( preCourse.isCyclic() ) {
                        return true;
                    }
                }
                
                vis = false;
                done = true;
                return false;
            }
        }
        
            
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            Course clist[] = new Course[numCourses];
            
            for(int i=0; i<numCourses; i++) {
                clist[i] = new Course();
            }
            
            for(int[] couple: prerequisites ) {
                Course c1 = clist[couple[0]];
                Course c2 = clist[couple[1]];
                c1.addPre(c2);
            }
            
            for(int i=0; i<numCourses; i++) {
                if( clist[i].isCyclic() ) {
                    return false;
                }
            }
            
            return true;
        }
    }

  • 0
    J

    This is fantastic~!


  • 0
    A

    vis = false;

    nitpick: this is redundant

    Thanks for sharing:)


  • 0
    A

    Thanks angelvivienne for pointing it. You're right. I just wanted to keep it's value consistent.


  • 0
    L

    Dude your solution is super fast!! My solution took 600ms...


  • 10
    P

    We had basically the same idea but I moved the isCyclic() out to look more OO.

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Course[] courses = new Course[numCourses];
        for (int i = 0; i < numCourses; i++) {
            courses[i] = new Course();
        }
        for (int i = 0; i < prerequisites.length; i++) {
            courses[prerequisites[i][0]].add(courses[prerequisites[i][1]]);
        }
        for (int i = 0; i < numCourses; i++) {
            if(isCyclic(courses[i])) return false;
        }
        return true;
    }
    
    private boolean isCyclic(Course cur) {
        if (cur.tested == true) return false;
        if (cur.visited == true) return true;
        cur.visited = true;
        for (Course c : cur.pre) {
            if (isCyclic(c)) {
                return true;
            }
        }
        cur.tested = true;
        return false;
    }
    
    class Course {
        boolean visited = false;
        boolean tested = false;
        List<Course> pre = new ArrayList<Course>();
        public void add(Course c) {
            pre.add(c);
        }
    }

  • 0
    T

    Nice solution!
    Can you please provide suggestions to my answer as well:
    https://leetcode.com/discuss/60669/logical-and-easy-to-understand-how-to-improve


  • 0
    G

    Great solution!


Log in to reply
 

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