跳转至

基环树⚓︎

对于一个连通图 G，如果其点数与边数相等，称它为一个基环树（\text{Pseudotree}）。也就是说，基环树是一个包含恰好一个环的连通图。

发现环

给定一个包含 n 个点和 n 条边的无向图，图中恰有一个环。请你找出环上的所有点。

Hint

对于无向图，可以将每条边视为双向边。统计每个点的度数，环上的点度数至少为 2，而树枝上的点度数为 1。通过拓扑排序可以将所有树枝上的点剔除，剩下的即为环上的点。

C++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int n;
  cin >> n;
  vector<vector<int>> g(n + 1);
  vector<int> in_degree(n + 1, 0);
  for (int i = 1; i <= n; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    in_degree[v]++;
    g[v].push_back(u);
    in_degree[u]++;
  }

  vector<bool> visited(n + 1, false);
  queue<int> q;
  for (int i = 1; i <= n; ++i) {
    if (in_degree[i] == 1) {  // 树枝上的点入度为 1
      q.push(i);
      visited[i] = true;
    }
  }
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int y : g[x]) {
      if (--in_degree[y] == 1) {
        q.push(y);
        visited[y] = true;
      }
    }
  }
  for (int i = 1; i <= n; ++i) {  // 环上的点未被访问
    if (!visited[i]) { cout << i << ' '; }
  }
  return 0;
}

内向基环树⚓︎

基环内向树（\text{Inward Pseudotree}）：有向弱连通图每个点的出度都为 1。

常常将内向基环树与拓扑排序结合使用，以求出每个点到环的距离。对于环上的点，到环的距离定义为 0；对于树枝上的点，到环的距离定义为其到环上最近点的距离。

在一些具体题目中，还会额外把环的大小作为环上节点的初始值，再向树枝部分做转移统计；这属于题目特定定义，不是“到环距离”的通用定义。

环上的点与树枝上的点可以通过统计入度来区分。环上的点入度至少为 1，而树枝上的点入度为 0。通过拓扑排序可以将所有树枝上的点剔除，剩下的即为环上的点。随后可以通过 BFS 从环上点开始，向树枝上扩展，计算每个点距离环的距离。

参加会议的最多员工数

一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张圆形的桌子，可以坐下任意数目的员工。

员工编号为 0 到 n - 1 。每位员工都有一位喜欢的员工，每位员工当且仅当他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工不会是他自己。

给你一个下标从 0 开始的整数数组 favorite，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的最多员工数目。

C++
#include <queue>
#include <vector>
using namespace std;

class Solution {
 public:
  int maximumInvitations(vector<int> &favorite) {
    int n = favorite.size();
    vector<int> in_degree(n);
    for (int edge : favorite) { ++in_degree[edge]; }
    queue<int> q;
    for (int i = 0; i < n; ++i) {
      if (in_degree[i] == 0) { q.push(i); }
    }
    vector<int> depth(n, 1);
    while (!q.empty()) {  // (1)!
      int x = q.front();
      q.pop();
      int y    = favorite[x];
      depth[y] = max(depth[y], depth[x] + 1);
      if (--in_degree[y] == 0) { q.push(y); }
    }
    int max_ring_size = 0, sum_chain_size = 0;
    for (int i = 0; i < n; ++i) {
      if (in_degree[i] == 0) { continue; }

      in_degree[i]  = 0;  // 将基环上的点的入度标记为 0，避免重复访问
      int ring_size = 1;
      for (int v = favorite[i]; v != i; v = favorite[v]) {  // 遍历基环上的点
        in_degree[v] = 0;
        ++ring_size;
      }
      if (ring_size == 2) {  // 基环大小为 2，累加两条最长链的长度
        sum_chain_size += depth[i] + depth[favorite[i]];
      } else {  // 基环大小大于 2，只能独立成团，更新最大基环大小
        max_ring_size = max(max_ring_size, ring_size);
      }
    }
    return max(max_ring_size, sum_chain_size);
  }
};

  1. 对于其他更复杂的性质，可以在拓扑排序过程中构建反图，反图中只包含树枝上的点，从而在后续处理中可以区分环上点与树枝上点。

外向基环树⚓︎

基环外向树（\text{Outward Pseudotree}）：有向弱连通图每个点的入度都为 1。

处理方式与内向基环树类似，只需将入度改为出度即可。

评论