LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 这类问题本质是检查图是否为有向无环图（DAG，Directed Acyclic Graph）

有向无环图
a->b->c->d
   ↓  ↓
   e->f

非有向无环图（bcfe 形成有向回路）
a->b->c->d
   ↑  ↓
   e<-f

• 现实世界中，一项工程可分为多个子工程，每个子工程可称为一个活动（Activity），这些活动可能存在先后关系。用点表示每个活动，用有向边表示先后关系，由此即可画出整个工程的有向图。这种用顶点表示活动的有向图称为 AOV 网（Activity On Vertex Network）

课程学习工程图的 AOV 网
a->b->c->d
   ↓  ↓
   e->f

a：离散数学
b：数据结构
a->b 表示学习 b 之前需要先学习 a

• AOV 网中不能存在回路。如果存在回路，则意味着一个活动的先行条件是其本身，这样显然会导致该活动无法完成，整个工程也就无法进行

a->b->c->d
   ↑  ↓
   e<-f

学习 b 之前要学习 a 和 e，a 可以学习
学习 e 之前要学习 f
学习 f 之前要学习 c
学习 c 之前要学习 b
陷入死循环

• 检查回路的方法是，对有向图做拓扑排序，如果能得到拓扑序列，则说明该图是有向无环图

a->b->c->d
   ↓  ↓
   e->f

对于图中的任意一条边的两个顶点 xy，如果 x-> y，则线性序列中 x 出现在 y 之前
满足这一条件的线性序列即为拓扑序列，如 abcdef 就是一个拓扑序列
    ________
   |        ↓
a->b->c->d  e->f
      |________↑

从有向图构建拓扑序列的过程即为拓扑排序，其过程如下：

选择一个无前驱节点的点，添加到线性序列：
a

从图中删除该顶点，并删除所有从它出发的有向边：
b->c->d
↓  ↓
e->f

继续选择一个无前驱节点的点，添加到线性序列：
ab

从图中删除该顶点，并删除所有从它出发的有向边：
   c->d
   ↓
e->f

继续选择一个无前驱节点的点（e 和 c 均可），添加到线性序列：
abe

从图中删除该顶点，并删除所有从它出发的有向边：
c->d
↓
f

继续选择一个无前驱节点的点，添加到线性序列：
abec

从图中删除该顶点，并删除所有从它出发的有向边：
  d

f

重复上述步骤，直到从图中删去所有顶点：
abecdf

    _____
   |     ↓
a->b->e  c->d  f
      |  |_____↑
      |________|

由上述过程可知，拓扑序列并不唯一

• 对于带环的有向图，无法用拓扑排序构造拓扑序列

a->b->c->d
   ↑  ↓
   e<-f

选择一个无前驱节点的点，添加到线性序列：
a

从图中删除该顶点，并删除所有从它出发的有向边：
b->c->d
↑  ↓
e<-f

继续选择一个无前驱节点的点，添加到线性序列
此时无满足条件的点，因此构造结束，最后的序列为 a，不为拓扑序列

• 对于该题，构造有向图，再对图拓扑排序，检查能否得到拓扑序列即可。这里采用邻接表存储有向图

class Solution {
 public:
  bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    unordered_map<int, vector<int>> m;  // 邻接表（节点及其所有后继节点）
    vector<int> indegree(numCourses);  // 节点的入度（以该点为后继节点的边数）
    for (auto& x : prerequisites) {
      m[x[1]].emplace_back(x[0]);  // 题目中 x[1] 是前驱节点，x[1]->x[0]
      ++indegree[x[0]];            // x[0] 入度加 1
    }
    queue<int> q;
    for (int i = 0; i < size(indegree); ++i) {
      if (!indegree[i]) {
        q.emplace(i);  // 把入度为 0 的点添加到队列中
      }
    }
    int cnt = 0;
    while (!empty(q)) {
      int n = q.front();  // 入度为 0 的点
      q.pop();            // 取出该点
      ++cnt;
      for (auto& x : m[n]) {  // 遍历该点所有后继节点
        --indegree[x];  // 因为删除了当前节点，后继节点入度减一
        if (!indegree[x]) {
          q.emplace(x);  // 如果后继节点入度为 0 则推入队列中
        }
      }
    }
    return cnt == numCourses;  // 遍历了所有点则说明是有向无环图
  }
};