Leetcode - Course Schedule

My code:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    private int V = 0;
    private ArrayList<List<Integer>> adj;
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        V = numCourses;
        adj = new ArrayList<List<Integer>>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < prerequisites.length; i++) {
            adj.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        
        int[] indegree = new int[V];
        for (int i = 0; i < V; i++) {
            for (Integer temp : adj.get(i)) {
                indegree[temp]++;
            }
        }
        
        Queue<Integer> q = new LinkedList<Integer>();
        for (int i = 0; i < V; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }
        
        if (q.isEmpty()) {
            return false;
        }
        
        int counter = 0;
        while (!q.isEmpty()) {
            Integer node = q.poll();
            for (Integer temp : adj.get(node)) {
                indegree[temp]--;
                if (indegree[temp] == 0) {
                    q.offer(temp);
                }
            }
            counter++;
        }
        
        if (counter != V) {
            return false;
        }
        else {
            return true;
        }
    }
}

这道题目的本质在于，如何判断一个图中是否存在 circle

然后有两种方法：
BFS, DFS

我个人更偏爱于 BFS

首相介绍下，什么是 topological sort
就是将一堆有dependency 的结点按照先后顺序输出出来。
这个介绍的不错。：
http://www.stoimen.com/blog/2012/10/01/computer-algorithms-topological-sort-of-a-graph/

必须是有向无环图 DAG

如何表示一个有向图。可以是链表，也可以是稀疏矩阵

一个DAG，他一定至少有一个入度为0的结点，一个出度为0的结点。

所以，如果我们从入度入手，先把入度为0的结点删除了。
然后再把删除后重新成为入度为0的结点删除了。
依次循环，最后，如果，删除的结点个数不等于图总结点个数，那么，就是有环图。
http://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/
这就是上面这个算法的思想。
写的还是很巧妙地。

下面说下 DFS
借鉴了这个思想：

http://www.geeksforgeeks.org/topological-sorting/

如果用 DFS实现 topological sort
其实相比于BFS，更简单，只用一味地DFS就行。

但是如果用来判断是否有环，就麻烦了。
于是我们需要维护一个set，然后每次进入一个节点，开始DFS
把访问过的结点加入到set中，如果在这次dfs中，之后又再次碰到了这个点，那么就说明有重复，有环，就报错。
如果没问题，退回到这个结点的时候，千万记得，把这个结点从set中删去，因为其他路径可能再次包含这个结点

同时，还需要维护一个总的布尔数组，来表示哪些结点已经被访问过了，不用再进行判断了。

My code:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    private int V = 0;
    private ArrayList<List<Integer>> adj;
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        V = numCourses;
        adj = new ArrayList<List<Integer>>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < prerequisites.length; i++) {
            adj.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        
        boolean[] isVisited = new boolean[V];
        for (int i = 0; i < V; i++) {
            if (!isVisited[i]) {
                boolean flag = visit(i, isVisited, new HashSet<Integer>());
                if (!flag) {
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean visit(int node, boolean[] isVisited, HashSet<Integer> set) {
        if (set.contains(node)) {
            return false;
        }
        set.add(node);
        isVisited[node] = true;
        for (Integer temp : adj.get(node)) {
            boolean flag = visit(temp, isVisited, set);
            if (!flag) {
                return false;
            }
        }
        set.remove(node);
        return true;
    }
}

reference:
https://discuss.leetcode.com/topic/17273/18-22-lines-c-bfs-dfs-solutions

Anyway, Good luck, Richardo! -- 09/09/2016

My code:

public class Solution {
    private Map<Integer, Set<Integer>> adj;
    private int[] degree;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        adj = new HashMap<Integer, Set<Integer>>();
        degree = new int[numCourses];
        
        for (int i = 0; i < prerequisites.length; i++) {
            int src = prerequisites[i][1];
            int dest = prerequisites[i][0];
            if (!adj.containsKey(src)) {
                adj.put(src, new HashSet<Integer>());
            }
            if (!adj.get(src).contains(dest)) {
                adj.get(src).add(dest);
                degree[dest]++;
            }
        }
        
        Queue<Integer> q = new LinkedList<Integer>();
        for (int i = 0; i < numCourses; i++) {
            if (degree[i] == 0) {
                q.offer(i);
            }
        }
        
        int total = 0;
        while (!q.isEmpty()) {
            Integer curr = q.poll();
            total++;
            if (adj.containsKey(curr)) {
                for (Integer nei : adj.get(curr)) {
                    degree[nei]--;
                    if (degree[nei] == 0) {
                        q.offer(nei);
                    }
                }
            }
        }
        
        return total == numCourses;
    }
}

要注意，可能输入边会重复, 所以要用set，并且初始化图时要检查。
而且， [1] 是 src, [0] 是 dest

Anyway, Good luck, Richardo! -- 10/17/2016

Leetcode - Course Schedule

推荐阅读更多精彩内容