ch09 课堂参考代码

ch09 拓扑排序与基环树

拓扑排序

• 在一些场景中，需要完成一系列事情，这些事情之间有顺序关系或者依赖关系，在做一件事情之前必须先做另一件事，例如课程学习的先后顺序，这类问题可以抽象为图论中的拓扑排序问题。

• 拓扑排序要解决的问题是给一个有向无环图（Directed Acyclic Graph，缩写是 DAG）的所有结点排序。

• 排序规则是如果图中存在一条边 $u\to v$ ，则结点 u 必须排在 v 之前。

• 相关概念：

  • 入度：以结点 v 为终点的边的数量称为 v 的入度。也就是“连进来的边”的数量。
  • 出度：以结点 u 为起点的边的数量称为 u 的出度。也就是“连出去的边”的数量。

• 拓扑排序步骤：

  • 找到所有入度为 0 的结点，显然这些结点应该排在前面（具体谁先谁后没有关系）。用一个容器（队列）储存当前我们找到的入度为 0 的结点。
  • 每次取出一个入度为 0 的结点 $u$，此时 $u$ 就是拓扑序列中的下一个结点。
  • 对于 $u$ 的每一条出边 $u\to v$，$v$ 的入度 -1（相当于删除 $u$、删除 $u$ 的出边，因为只关心入度，所以入度 -1 即可，不用真的执行删边操作）。
  • 如果 $v$ 的入度 -1 后变为了 0，那么将 v 放进容器（队列）中。
  • 重复上述操作，直到队列为空。

• 拓扑排序无解的判断：如果队列空了，但是还有点未进入队列，即这些点的入度都 > 0，说明图不是 DAG，不存在拓扑排序。

• 拓扑排序结果不唯一的判断：如果同时有多个入度为 0 的结点，前面说到具体谁先谁后没有关系，那么拓扑排序有多种可能的结果。具体的判断就是如果某一时刻队列里的元素个数 > 1，可以判定拓扑排序结果不唯一。

• 代码：

  void topo(int n) {
      queue<int> que;
      for (int i = 1; i <= n; i++) {
          if (in[i] == 0) que.push(i);
      }
      while (!que.empty()) { // while循环次数（入队次数），<n说明无解
          if (que.size() > 1) { } // 满足if说明拓扑排序不唯一
          int u = que.front(); // u是拓扑序列的下一个结点，要输出拓扑序列则在这里输出u
          que.pop();
          // 删除以结点u为起点的边，也就是边的终点入度-1
          for (int i = 0; i < G[u].size(); i++) {
              int v = G[u][i];
              in[v]--;
              if (in[v] == 0) {
                  que.push(v);
              }
          }
      }
  }
  

基环树

无向边的基环树

• n 个点的树有 n - 1 条边，再添加一条边则必然会出现一个环，除了环之外，其余部分是若干棵子树。

• 这种 n 个点 n 条边的连通无向图，称为“基环树”，可以把环看作基环树广义的“根结点”。

• 若干棵基环树组成的森林，称为“基环树森林”。显然基环树森林必然也是 n 个点 n 条边，但 n 个点 n 条边的无向图不一定是基环树森林。

• 对于基环树（森林）的处理，分为环外和环内两部分。

  • 环外部分

    • 与结点 u 相连的边的条数称为该结点的“度”或“度数”。

    • 环外最外围的结点度数是 1，从度数为 1 的结点开始，用类似拓扑排序的方法，环外的结点逐步入队，环内的结点无法入队，以此找出所有环外的结点。

    • 代码：

      vector<int> G[N];
      int deg[N];
      bool vis[N];
      void topo(int n) {
      	queue<int> que;
      	for (int i = 1; i <= n; i++) {
      		if (deg[i] == 1) que.push(i); // deg[i]表示结点i的度数
      	}
      	while (!que.empty()) {
      		int u = que.front();
      		que.pop();
      		vis[u] = true; // 标记结点u是环外的点
      		for (int v : G[u]) {
      			deg[v]--;
      			if (deg[v] == 1) que.push(v);
      		}
      	}
      }
      

  • 环内部分

    • 经过 topo() 的处理后，vis[u] == false 的结点 u 就是环中的点。
    • 如果需要遍历一个环中的点，从环中一个点出发，搜索其连通的所有 vis[] 为 false 的点即可。

有向边的基环树

• 有向图中，也有类似概念，如果每个结点有且仅有一条出边（即出度为 1），并且是弱连通的（即换成无向边后是连通的），称为“基环内向树”。可以尝试自己举一些例子画出来看看，环外的点都指向环的方向，好像以“基环”为中心，有向内收缩的趋势，所以叫“内向”。

• 若干棵基环内向树组成的森林，称为“基环内向树森林”。

• 同理，如果每个结点有且仅有一条入边（即入度为 1），则是“基环外向树”或“基环外向树森林”。

• 常常把“基环内向树”和“基环外向树”也简称为“基环树”。

• 只需要学习如何处理“基环内向树”，对于“基环外向树”把所有边换个方向也就转换为“基环内向树”问题。

• 对于基环内向树（森林）的处理，同样分为环外和环内两部分。

  • 环外部分同样用拓扑排序，入度为 0 的结点入队。

    // 因为只有一条出边，可以不用vector存图，nxt[u]记录u的出边终点即可
    int nxt[N], in[N]; // in[u]表示u的入度
    bool vis[N];
    void topo(int n) {
    	queue<int> que;
    	for (int i = 1; i <= n; i++) {
    		if (in[i] == 0) que.push(i); // 入度为0的结点入队
    	}
    	while (!que.empty()) {
    		int u = que.front();
    		que.pop();
    		vis[u] = true; // 标记结点u是环外的点
    		int v = nxt[u];
    		in[v]--;
    		if (in[v] == 0) que.push(v);
    	}
    }
    

  • 环内部分也类似无向边的基环树，先找到环内一个点，从这个点出发去搜索。因为每个点只有一条出边，用循环写也很方便，一直往前走，直到回到本身，就走完了整个环。

    int res = 0; // 记录换/内向基环数的个数
    for (int i = 1; i <= n; ++i) {
        if (vis[i]) continue; // 跳过环外的点和走过的点
        int p = i, cnt = 0; // 如果需要计算环的长度，记录中 cnt 中
        while (!vis[p]) vis[p] = 1, p = nxt[p], ++cnt;
        ++res;
    }