Course Schedule

發表於   |   分類於

Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

1
2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

1
2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

依赖关系判定，实际上就是一个拓扑结构，层序遍历可解。BFS每下降一层，其对应后续节点的入度减一，入度为0的节点入队列，如果最后所有节点的入度都为0，则返回true，否则返回false。

AC的C++代码：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<vector<int>> graphic(numCourses,vector<int>(0));
        vector<int> indegrees(numCourses,0);
        queue<int> q;

        for(auto it = prerequisites.begin(); it != prerequisites.end(); ++it)
        {
            int succ = it->first;
            int pre = it->second;
            indegrees[succ]++;
            graphic[pre].push_back(succ);
        }

        for (int i = 0 ; i < indegrees.size(); ++i)
        {
            if (indegrees[i] == 0)
            {
                q.push(i);
            }
        }

        while(q.size())
        {
            int n = q.front();
            q.pop();// 注意这里与C版本的顺序不一致。
            vector<int>& v = graphic[n];
            for (int i = 0; i < v.size(); ++i)
            {
                --indegrees[v[i]];
                if (indegrees[v[i]] == 0)
                {
                    q.push(v[i]);
                }
            }
        }

        for (int i = 0 ; i < indegrees.size(); ++i)
        {
            if (indegrees[i] != 0)
            {
                return false;
            }
        }

        return true;
    }
};

超过规定内存空间的C代码：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

bool canFinish(int numCourses, int** prerequisites, int prerequisitesRowSize, int prerequisitesColSize) {
    int* indegrees = (int*)malloc(numCourses*sizeof(int));
    int** graphic = (int**)malloc(sizeof(int*) * numCourses);
    int * queue = (int*)malloc(numCourses*sizeof(int));
    int begin = 0;
    int end = 0;
    for (int i = 0 ; i < numCourses; ++i)
    {
        indegrees[i] = 0;
    }

    for (int i = 0 ; i < numCourses; ++i)
    {
        graphic[i] = (int*)malloc(sizeof(int*) * numCourses);
        for (int j = 0 ; j < numCourses; ++j)
        {
            graphic[i][j] = -1;
        }
    }

    for (int i = 0 ;i < prerequisitesRowSize; ++i)
    {
        int* row = prerequisites[i];
        int succ = row[0];
        int pre = row[1];
        indegrees[succ]++;//后续课程入度加一
        graphic[pre][succ] = 1;//设置前导课程的后续边
    }
    //找出所有入度为0的点作为起始节点
    for(int i = 0; i < numCourses; ++i)
    {
        if (indegrees[i] == 0)
        {
            queue[end++] = i;
        }
    }
    // BFS
    while(begin != end)
    {
        int n = queue[begin];
        //查找所有n的后继节点，每处理一次，后续节点入度减一，如果后续节点入度为0，那么就加入队列
        for (int i = 0 ; i < numCourses; ++i)
        {
            if (graphic[n][i] == 1)
            {
                --indegrees[i];
                if (indegrees[i] == 0)
                {
                    queue[end++] = i;
                }
            }
        }
        ++begin;
    }

    //如果最后还有入度不为0的节点，返回false
    for (int i = 0 ; i < numCourses; ++i)
    {
        if (indegrees[i] != 0)
        {
            return false;
        }
    }
    return true;
}