微软面试题： LeetCode 207. 课程表出现次数：3

题目描述：

给定 n 门课程（0，n-1）和它们之间的先修关系，比如{（0,1），（1,2），（2,3），（2,0）} ,（0,1）表示课程 1 是课程 0

的先修课程，即要修课程 0 必须先修课程 1,。根据给出的课程和其之间的先修关系，判断能否完成所有课程的学习。

将给定的课程和课程之间的先修关系转化为有向图的形式，使用图的临接表（或逆临接表）的形式表示图 DAG 。

可以有两种思路对应两种算法：

方法一： bfs 实现的拓扑排序，拓扑排序最终剩下节点删不掉，则不能完成所有课程的学习。

代码如下：

 1 //方法一： bfs 实现的拓扑排序
 2     bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
 3     {
 4        vector<vector<int>> r_adjcent(numCourses);//用逆临接表 表示图
 5        vector<int> out_degree(numCourses);//统计各个节点的出度
 6        queue<int> q;//出度为 0 的节点入栈(没有先修课)
 7        for(int i = 0; i < prerequisites.size();++i)
 8        {
 9            int out_i = prerequisites[i][0];
10            int in_i = prerequisites[i][1];
11            r_adjcent[in_i].push_back(out_i);
12            out_degree[out_i]++;
13        }
14        for(int i = 0; i < out_degree.size();++i)
15        {
16            if(out_degree[i] == 0)
17            {
18                q.push(i);
19            }
20        }
21        while (!q.empty())
22        {
23            int no_pre = q.front(); //没有先修课的节点
24            q.pop();
25            for(int i = 0; i < r_adjcent[no_pre].size();++i)
26            {
27                int out_tmp = r_adjcent[no_pre][i];
28                if(--out_degree[out_tmp] == 0)
29                {
30                    q.push(out_tmp);
31                }
32            }
33            --numCourses;
34        }
35        return numCourses == 0;
36     }
37

方法二： dfs 判定课程关系的有向图是否有圈，有圈就不能完成所有课程的学习

代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 // dfs 判断有向图是否有圈
 4 class Solution {
 5 public:
 6     bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
 7     {
 8        vector<vector<int>> adjcent(numCourses);//用临接表 表示图
 9        vector<int> visted(numCourses,0);
10        for(int i = 0; i < prerequisites.size();++i)
11        {
12            int post_i = prerequisites[i][0];
13            int pre_i = prerequisites[i][1];
14            adjcent[post_i].push_back(pre_i);
15        }
16        for(int k = 0; k < numCourses;++k)
17        {
18            if(has_circle(k,adjcent,visted))//有圈直接返回 fasle
19            {
20                return false;
21            }
22        }
23        return true;
24     }
25 
26     bool has_circle(int i,vector<vector<int>> &adjcent,vector<int> &visted)
27     {
28         if(visted[i] == -1)
29         {
30             return false;
31         }
32         if(visted[i] == 1)
33         {
34             return true;
35         }
36         visted[i] = 1;
37         for(int j = 0; j < adjcent[i].size();++j)
38         {
39             int node = adjcent[i][j];
40             if(has_circle(node,adjcent,visted))
41             {
42                 return true;
43             }
44         }
45         visted[i] = -1;//从节点 i dfs 遍历，无圈
46         return false;
47     }
48 };

微软面试题： LeetCode 207. 课程表 出现次数：3

微软面试题： LeetCode 207. 课程表出现次数：3