PigyChan_LeetCode 207. 课程表

207. 课程表

难度中等

你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

示例 1:

输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:

输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

提示：
1. 输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法。
2. 你可以假定输入的先决条件中没有重复的边。
3. 1 <= numCourses <= 10^5

思路1.0(已看题解):

广度优先搜索
通过题目所给条件构造一个拓扑排序，若最终构成的拓扑排序节点数<n,则判断false.
那么怎么构造拓扑排序呢?
(1)先为所有节点构造一个入度列表:indgree,indgree[i]记录着第i个节点的入度数.
(2)构造一个队列来存储所有入度为0的节点,这些就是没有前继,可以加入拓扑排序的节点
(3)队列中的节点加入拓扑排序的时候要将其弹出队列,同时要对该节点的所有后继节点做处理:他们的入度全要-1.即代表他们的前继条件满足了一个了,如此循环直到队列为空.
(4)为了方便找到每个节点的后继邻接节点，为该图创建一个邻接表

代码1.0(已完成):

  class Solution {
  public:
      bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
          vector<int> indegree(numCourses,0);     //入度表
          vector<vector<int>> adjacency(numCourses);     //邻接表
          queue<int> que;
          int topoNum = 0;
          //先处理好入度表和邻接表
          for (const auto& i : prerequisites)
          {
              ++indegree[i[0]];
              adjacency[i[1]].push_back(i[0]);
          }
          //所有没有前继条件的节点压入队列中
          for (int i = 0; i < numCourses; ++i)
          {
              if (indegree[i] == 0)
              {
                  que.push(i);
                  ++topoNum;
              }
          }
          while (!que.empty())
          {
              //从队列中取一个节点构造拓扑
              int valueNow = que.front();
              que.pop();
              
              //该点的所有后继点 -1 前继数
              for (auto& i : adjacency[valueNow])
              {
                  --indegree[i];
                  if (indegree[i] == 0)
                  {
                      que.push(i);
                      ++topoNum;
                  }
              }
          }
          return topoNum==numCourses;
      }
  };
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

思路2.0(已看题解):

深度优先算法
总的思想就是判断题目所给的有向图是否存在环路,其具体实施过程如下:
(1)将题目所给的信息存在一个邻接表中.
(2)定义一个flag数组,它的三种变量 0 1 -1 分别标识了 “没被访问” “被当前节点访问过了” “在之前的搜索中检验过了”.
(3)在深度优先搜索中 如果flag[i]==0,那么flag[i]=1,遍历下一个
(4)如果flag[i]1,那么说明我们这是第二次访问该节点了,存在环路,return false;
(5)如果flag[i]-1,那么说明这个节点已经完全判断处理过了,遍历下一个
(6)如果一个点完成了深度优先搜索且不存在环路,那么flag[i]=-1;

代码2.0:

  class Solution {
  public:
      bool dfs(int nowNode, vector<int>& flag, const vector<vector<int>>& adjacency)
      {
          if (flag[nowNode] == 1) return false;
          if (flag[nowNode] == -1) return true;


          if (flag[nowNode] == 0)
          {
              flag[nowNode] = 1;
              //以该节点为起点进行深度搜索
              for (const auto& i : adjacency[nowNode])
                  if (!dfs(i, flag, adjacency)) return false;
              flag[nowNode] = -1;
              return true;
          }
          return true;
      }


      bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
          vector<vector<int>> adjacency(numCourses);
          vector<int> flag(numCourses, 0);
          
          for (const auto& i : prerequisites)
              adjacency[i[1]].push_back(i[0]);


          for (int i = 0; i < numCourses; ++i)
              if (!dfs(i, flag, adjacency)) return false;


          return true;
      }
  };

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