Course Schedule

本质上是检测图中是否成环。图是DG, 看是否是DAG.

  1. array of ArrayList: ArrayList[] graph = new ...
  2. 数组，数组中都是ArrayList
  3. 初始化这些 ArrayList
  4. 给所有的 ArrayList 赋值
  5. 创建并初始化赋值Queue
  6. bfs queue
  7. 根据所有的节点的indegree是否都为0判断DG是否是DAG

Java: 

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
public boolean canFinish(int numCourses, int[][] prerequisites) {
    ArrayList[] graph = new ArrayList[numCourses];
    int[] in = new int[numCourses];
    for (int i = 0; i < numCourses; ++i) {
        graph[i] = new ArrayList<>();
    }
    for (int[] p : prerequisites) {
        graph[p[1]].add(p[0]);
        in[p[0]]++;
    }
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < numCourses; ++i) {
        if (in[i] == 0) q.offer(i);
    }
    while (!q.isEmpty()) {
        int pre = q.poll();
        for (int i = 0; i < graph[pre].size(); ++i) {
            int post = (int) graph[pre].get(i);
            --in[post];
            if (in[post] == 0) q.offer(post);
        }
    }
    for (int i = 0; i < numCourses; ++i) {
        if (in[i] != 0) return false;
    }
    return true;
}

关于上面的遍历写法，可以用foreach，不过因为是Object转化为ArrayList<Integer>所以需要强转一下:

1
2
3
4
5
6
7
while (!q.isEmpty()) {
    int pre = q.poll();
    for (Integer post : (ArrayList<Integer>) graph[pre]) {
        --in[post];
        if (in[post] == 0) q.offer(post);
    }
}

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses, vector<int>());
    vector<int> in(numCourses);
    for (auto a : prerequisites) {
        graph[a[1]].push_back(a[0]);
        ++in[a[0]];
    }
    queue<int> q;
    for (int i = 0; i < numCourses; ++i) {
        if (in[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int t = q.front(); q.pop();
        for (int i : graph[t]) {
            --in[i];
            if (in[i] == 0) q.push(i);
        }
    }
    for (int i = 0; i < numCourses; ++i) {
        if (in[i] != 0) return false;
    }
    return true;
}