Intuitive Java solution


  • 0

    Warning: this is not an optimal solution. In fact, it's far from optimal solution. But it's naive enough to understand.

    First of all, we have all nodes (courses) that have no relation with each other.
    When we get a prerequisite rule. We detect whether the two courses have connections in opposite direction. If yes we return false, otherwise add the prerequisite and keep going.

    In the end, we return true, because we already look through all prerequisites.

    public class Solution {
        public class Node {
            public int val;
            public List<Node> nodes;
            public Node(int val) {
                this.val = val;
                this.nodes = new ArrayList<Node>();
            }
        }
    
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            Node[] depend = new Node[numCourses];
            for (int i = 0; i < numCourses; i++) {
                depend[i] = new Node(i);
            }
    
            for (int[] rule : prerequisites) {
                Node n1 = depend[rule[0]];
                Node n2 = depend[rule[1]];
                if (this.isConnect(n2, n1)) {
                    return false;
                }
                n1.nodes.add(n2);
            }
            return true;
        }
    
        private boolean isConnect(Node n1, Node n2) {
            for (Node node : n1.nodes) {
                if (node == n2 || this.isConnect(node, n2)) {
                    return true;
                }
            }
            return n1 == n2;
        }
    }
    

    There're bunch of strategy can used to improve performance and time complexity:

    1. directly use List instead of Node

    2. precompute the connection when add edges

    3. don't use 2, but cache the connect relation

    For example:

    public class Solution {
        List<Integer>[] depend;
    
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            depend = new List[numCourses];
            for (int i = 0; i < numCourses; i++) {
                depend[i] = new ArrayList<Integer>();
            }
    
            for (int[] rule : prerequisites) {
                if (this.isConnect(rule[1], rule[0])) {
                    return false;
                }
                depend[rule[0]].add(rule[1]);
            }
            return true;
        }
    
        private boolean isConnect(int u, int v) {
            for (Integer node : depend[u]) {
                if (node == v || this.isConnect(node, v)) {
                    return true;
                }
            }
            return false;
        }
    }

Log in to reply
 

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