连通性⚓︎

图的连通性指的是图中顶点之间的可达性。

在无向图中，如果任意两个顶点之间存在路径相互可达，则称该图为连通图；否则称为非连通图。

在有向图中，如果任意两个顶点之间存在路径相互可达，则称该图为强连通图；如果有向图的基图（将有向边视为无向边）是连通的，则称该图为弱连通图；否则称为非连通图。

强连通分量⚓︎

强连通分量（ $\text{Strongly Connected Component}$ , $\text{SCC}$ ）是指在有向图中，任意两个顶点之间都存在路径相互可达的最大子图。 $\text{Tarjan}$ 算法可以在线性时间内找到图中的所有强连通分量。

$\text{Tarjan}$ 算法求解强连通分量的核心思想是使用深度优先搜索（ $\text{DFS}$ ）遍历图，并利用时间戳（ $timer$ ）和栈来跟踪当前路径上的节点。每个节点在被访问时会被赋予一个唯一的时间戳（ $dfn$ ），同时维护一个低链接值（ $low$ ），表示从该节点出发能够到达的最早节点的时间戳。当遍历完成后，如果某个节点的时间戳等于其低链接值，则说明该节点是一个强连通分量的根节点，可以将栈中的节点弹出，形成一个强连通分量。

$\text{Tarjan}$ 算法求得的强连通分量具有以下性质：

每个强连通分量都是图的最大子图，且任意两个节点之间都存在路径相互可达。
强连通分量之间的关系可以形成一个有向无环图（ $\text{DAG}$ ），即强连通分量之间不存在环路。
强连通分量的划分是唯一的，即对于同一个有向图，无论使用何种方法求解，得到的强连通分量划分都是相同的。
强连通分量编号按照拓扑排序的逆序进行编号，即编号较小的强连通分量在拓扑排序中位于后面。

强连通分量

给定一个有向图，求出图中的所有强连通分量。输出强连通分量的个数以及每个强连通分量中的点，要求每个强连通分量内的点按字典序排序，强连通分量之间也按字典序排序。

C++

#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n + 1);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
  }

  vector<int> dfn(n + 1);
  vector<int> low(n + 1);     // 从该点出发所能到达的最小时间戳
  vector<int> scc_id(n + 1);  // 该点所在的SCC编号

  stack<int> st;              // 当前SCC中的点
  vector<bool> visit(n + 1);  // 表示是否在当前的SCC中

  int timer = 0, scc_count = 0;
  auto tarjan = [&](auto &&self, int u) -> void {
    dfn[u] = low[u] = ++timer;
    st.push(u);
    visit[u] = true;
    for (int v : g[u]) {
      if (!dfn[v]) {  // v未被访问, 继续DFS
        self(self, v);
        low[u] = min(low[u], low[v]);
      } else if (visit[v]) {  // v在当前SCC中, 更新low[u]
        low[u] = min(low[u], dfn[v]);
      }
    }
    if (dfn[u] == low[u]) {        // u是当前SCC的首节点
      for (int x = -1; x != u;) {  // 将该SCC中点全部出栈
        x = st.top();
        st.pop();
        visit[x]  = false;      // 将x移出当前SCC
        scc_id[x] = scc_count;  // 标记x所属的SCC编号
      }
      ++scc_count;
    }
  };

  for (int i = 1; i <= n; i++) {
    if (dfn[i] == 0) { tarjan(tarjan, i); }
  }

  vector<vector<int>> scc(scc_count);
  for (int i = 1; i <= n; i++) { scc[scc_id[i]].push_back(i); }

  cout << scc.size() << '\n';
  // 输出每个强连通分量中的点, 按照字典序排序
  for (auto &component : scc) { sort(component.begin(), component.end()); }
  sort(scc.begin(), scc.end());
  for (const auto &component : scc) {
    for (int v : component) { cout << v << ' '; }
    cout << '\n';
  }

  return 0;
}

利用强连通分量可以将有向图进行缩点，得到一个有向无环图（ $\text{DAG}$ ）。在缩点后的图中，每个强连通分量被视为一个单独的节点，强连通分量之间的边则表示原图中不同强连通分量之间的连接关系。缩点后的有向无环图具有以下性质：

缩点后的图中不存在环路，因为强连通分量之间的连接关系是单向的。
可以在缩点后的图上进行拓扑排序，从而确定强连通分量之间的依赖关系。
可以在缩点后的图上进行动态规划等算法，从而解决原图中的一些复杂问题。

【模板】缩点

给定一个有向图，每个点有一个权值。求从某个点出发，经过若干条边后所能获得的最大权值和。经过的点的权值只计算一次。

C++

#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<int> weight(n + 1);
  for (int i = 1; i <= n; ++i) { cin >> weight[i]; }
  vector<vector<int>> g(n + 1);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
  }

  vector<int> dfn(n + 1);
  vector<int> low(n + 1);     // 从该点出发所能到达的最小时间戳
  vector<int> scc_id(n + 1);  // 该点所在的SCC编号

  stack<int> st;              // 当前SCC中的点
  vector<bool> visit(n + 1);  // 表示是否在当前的SCC中

  int timer = 0, scc_count = 0;
  auto tarjan = [&](auto &&self, int u) -> void {
    dfn[u] = low[u] = ++timer;
    st.push(u);
    visit[u] = true;
    for (int v : g[u]) {
      if (!dfn[v]) {  // v未被访问, 继续DFS
        self(self, v);
        low[u] = min(low[u], low[v]);
      } else if (visit[v]) {  // v在当前SCC中, 更新low[u]
        low[u] = min(low[u], dfn[v]);
      }
    }
    if (dfn[u] == low[u]) {        // u是当前SCC的首节点
      for (int x = -1; x != u;) {  // 将该SCC中点全部出栈
        x = st.top();
        st.pop();
        visit[x]  = false;      // 将x移出当前SCC
        scc_id[x] = scc_count;  // 标记x所属的SCC编号
      }
      ++scc_count;
    }
  };

  for (int i = 1; i <= n; i++) {
    if (dfn[i] == 0) { tarjan(tarjan, i); }
  }

  vector<vector<int>> dag(scc_count);
  vector<int> scc_weight(scc_count);
  for (int i = 1; i <= n; i++) { scc_weight[scc_id[i]] += weight[i]; }
  for (int u = 1; u <= n; ++u) {
    for (int v : g[u]) {  // 构建缩点后的DAG
      if (scc_id[u] != scc_id[v]) { dag[scc_id[u]].push_back(scc_id[v]); }
    }
  }

  vector<int> dp(scc_count);
  int answer = 0;

  // 拓扑排序+DP
  vector<int> in_degree(scc_count);
  for (int u = 0; u < scc_count; ++u) {  // 计算入度
    for (int v : dag[u]) { in_degree[v]++; }
  }

  queue<int> q;
  for (int i = 0; i < scc_count; ++i) {
    if (in_degree[i] == 0) { q.push(i); }
    dp[i] = scc_weight[i];
  }

  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : dag[u]) {
      dp[v] = max(dp[v], dp[u] + scc_weight[v]);
      if (--in_degree[v] == 0) { q.push(v); }
    }
    answer = max(answer, dp[u]);
  }

  cout << answer << '\n';
  return 0;
}

Note

完成 $\text{DAG}$ 的构建后最好去重, 因为可能有多条边连向同一个SCC。如果不影响答案不去重也没关系, 只是会多做一些重复计算，影响效率。或者使用 set 代替 vector 存储边。
C++
```
for (int i = 0; i < scc_count; ++i) {
  sort(dag[i].begin(), dag[i].end());
  dag[i].erase(unique(dag[i].begin(), dag[i].end()), dag[i].end());
}
```

在缩点后的 $\text{DAG}$ 上可以使用拓扑排序加动态规划（ $\text{DP}$ ）的方法求解最大权值和问题。也可以使用深度优先搜索（ $\text{DFS}$ ）的记忆化搜索方法实现。

C++

vector<int> visit_dag(scc_count);
auto dfs = [&](auto &&self, int u) -> int {
  if (visit_dag[u]) { return dp[u]; }
  visit_dag[u] = 1;
  for (int v : dag[u]) {
    dp[u] = max(dp[u], self(self, v) + scc_weight[u]);
  }
  return dp[u];
};

for (int i = 0; i < scc_count; ++i) {
  answer = max(answer, dfs(dfs, i));
}

受欢迎的牛 G

给定一个有向图，求图中是否存在一个强连通分量，使得所有其他强连通分量都可以通过有向边到达该强连通分量。如果存在这样的强连通分量，输出该强连通分量中节点的数量；否则输出 0。

C++

#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m;
  cin >> n >> m;

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

  vector<int> dfn(n + 1);
  vector<int> low(n + 1);     // 从该点出发所能到达的最小时间戳
  vector<int> scc_id(n + 1);  // 该点所在的SCC编号

  stack<int> st;              // 当前SCC中的点
  vector<bool> visit(n + 1);  // 表示是否在当前的SCC中

  int timer = 0, scc_count = 0;
  auto tarjan = [&](auto &&self, int u) -> void {
    dfn[u] = low[u] = ++timer;
    st.push(u);
    visit[u] = true;
    for (int v : g[u]) {
      if (!dfn[v]) {  // v未被访问, 继续DFS
        self(self, v);
        low[u] = min(low[u], low[v]);
      } else if (visit[v]) {  // v在当前SCC中, 更新low[u]
        low[u] = min(low[u], dfn[v]);
      }
    }
    if (dfn[u] == low[u]) {        // u是当前SCC的首节点
      for (int x = -1; x != u;) {  // 将该SCC中点全部出栈
        x = st.top();
        st.pop();
        visit[x]  = false;      // 将x移出当前SCC
        scc_id[x] = scc_count;  // 标记x所属的SCC编号
      }
      ++scc_count;
    }
  };

  for (int i = 1; i <= n; i++) {
    if (dfn[i] == 0) { tarjan(tarjan, i); }
  }

  vector<vector<int>> dag(scc_count);
  vector<int> scc_weight(scc_count);
  for (int i = 1; i <= n; i++) { scc_weight[scc_id[i]] += 1; }
  for (int u = 1; u <= n; ++u) {
    for (int v : g[u]) {
      if (scc_id[u] != scc_id[v]) { dag[scc_id[u]].push_back(scc_id[v]); }
    }
  }

  int star_id = -1;
  for (int u = 0; u < scc_count; ++u) {
    if (dag[u].empty()) {
      if (star_id != -1) {  // 不止一个出度为0的SCC
        star_id = -1;
        break;
      }
      star_id = u;
    }
  }
  if (star_id == -1) {
    cout << 0 << '\n';
    return 0;
  }
  cout << scc_weight[star_id] << '\n';

  return 0;
}

割点⚓︎

割点（ $\text{Articulation Point}$ ）是指在无向图中，去掉该节点及其相关的边后，图的连通分量数量增加的节点。 $\text{Tarjan}$ 算法可以在线性时间内找到图中的所有割点。

割点的判定条件如下：

对于非根节点 $u$ ，如果存在一个子节点 $v$ ，使得从 $v$ 出发无法通过其他路径回到 $u$ 或 $u$ 的祖先节点（即 $low[v] \geq dfn[u]$ ），则 $u$ 是割点。
对于根节点 $u$ ，如果 $u$ 有两个或以上的子节点，则 $u$ 是割点。

$\text{Tarjan}$ 算法求解割点的核心思想是使用深度优先搜索（ $\text{DFS}$ ）遍历图，并利用时间戳（ $timer$ ）和低链接值（ $low$ ）来跟踪节点的访问情况。在遍历过程中，根据上述判定条件识别割点。

【模板】割点（割顶）

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

void solve() {}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m;
  cin >> n >> m;

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

  vector<int> dfn(n + 1);  // 遍历到该点的时间戳 depth first number
  vector<int> low(n + 1);  // 从该点出发所能到达的最小时间戳
  vector<int> articulation;

  int timer   = 0;
  auto tarjan = [&](auto &&self, int u, int from) -> void {
    dfn[u] = low[u] = ++timer;
    int child       = 0;
    bool valid      = false;
    for (int v : g[u]) {
      if (!dfn[v]) {
        ++child;
        self(self, v, u);
        if (low[v] >= dfn[u] && from != -1) { valid = true; }
        low[u] = min(low[u], low[v]);
      } else if (v != from) {
        low[u] = min(low[u], dfn[v]);
      }
    }
    if (valid || from == -1 && child >= 2) { articulation.push_back(u); }
  };
  for (int i = 1; i <= n; i++) {
    if (dfn[i] == 0) { tarjan(tarjan, i, -1); }
  }
  sort(articulation.begin(), articulation.end());
  cout << articulation.size() << "\n";
  for (int u : articulation) { cout << u << " "; }
  cout << "\n";
  return 0;
}

桥⚓︎

桥（ $\text{Bridge}$ ）是指在无向图中，去掉该边后，图的连通分量数量增加的边。 $\text{Tarjan}$ 算法可以在线性时间内找到图中的所有桥。

桥的判定条件如下：

对于一条边 $(u, v)$ ，如果从节点 $v$ 出发无法通过其他路径回到节点 $u$ 或 $u$ 的祖先节点（即 $low[v] > dfn[u]$ ），则该边是桥。

重边处理

如果图中可能存在重边，桥的模板不应只用 parent 顶点判断回边，而应记录“父边编号”并跳过与当前 DFS 树边对应的那一条边。否则在有重边时，可能会把本应作为返祖边处理的边错误忽略掉。

$\text{Tarjan}$ 算法求解桥

C++

vector<int> dfn(n + 1);  // 遍历到该点的时间戳 depth first number
vector<int> low(n + 1);  // 从该点出发所能到达的最小时间戳
vector<pair<int, int>> bridge;

int timer   = 0;
auto tarjan = [&](auto &&self, int u, int parent) -> void {
  dfn[u] = low[u] = ++timer;
  for (int v : g[u]) {
    if (!dfn[v]) {
      self(self, v, u);
      if (low[v] > dfn[u]) { bridge.emplace_back(u, v); }
      low[u] = min(low[u], low[v]);
    } else if (v != parent) {
      low[u] = min(low[u], dfn[v]);
    }
  }
};

for (int i = 0; i < n; i++) {
  if (dfn[i] == 0) { tarjan(tarjan, i, -1); }
}

Network

给定一个无向图，图中有 $n$ 个节点和 $m$ 条边。然后进行 $q$ 次操作，每次操作增加一条边，询问当前图中桥的数量。

C++

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

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

  vector<int> dfn(n + 1);  // 遍历到该点的时间戳 depth first number
  vector<int> low(n + 1);  // 从该点出发所能到达的最小时间戳
  vector<int> bridge(n + 1);
  int bridge_count = 0;

  vector<int> parent(n + 1);
  vector<int> depth(n + 1);

  int timer   = 0;
  auto tarjan = [&](auto &&self, int u, int from) -> void {
    parent[u] = from;
    dfn[u] = low[u] = ++timer;
    for (int v : g[u]) {
      if (!dfn[v]) {
        depth[v] = depth[u] + 1;
        self(self, v, u);
        if (low[v] > dfn[u]) {
          bridge[v] = u;   // 标记该边为桥
          ++bridge_count;  // 桥数量加一
        }
        low[u] = min(low[u], low[v]);
      } else if (v != from) {
        low[u] = min(low[u], dfn[v]);
      }
    }
  };

  for (int i = 0; i < n; i++) {
    if (dfn[i] == 0) { tarjan(tarjan, i, -1); }
  }
  // 连边后形成环, 环上的桥都不再是桥
  auto get_lca = [&](int x, int y) {
    if (depth[x] > depth[y]) { swap(x, y); }  // 确保x深度更小
    while (depth[y] > depth[x]) {             // 提升y到和x同一深度
      if (bridge[y] != 0) {                   // 该边不再是桥
        bridge_count--;
        bridge[y] = 0;
      }
      y = parent[y];
    }
    if (y == x) { return; }  // 已经是同一个祖先
    while (x != y) {
      if (bridge[x] != 0) {
        bridge_count--;
        bridge[x] = 0;
      }
      if (bridge[y] != 0) {
        bridge_count--;
        bridge[y] = 0;
      }
      x = parent[x];
      y = parent[y];
    }
  };

  cout << "Case " << t << ":\n";
  int q;
  cin >> q;
  for (int i = 0; i < q; ++i) {
    int u, v;
    cin >> u >> v;
    get_lca(u, v);
    cout << bridge_count << "\n";
  }
  cout << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t = 1;
  int n, m;
  while (cin >> n >> m) {
    if (n == 0 && m == 0) { break; }
    solve(n, m, t);
    t++;
  }
  return 0;
}

连通性⚓︎

强连通分量⚓︎

割点⚓︎

桥⚓︎

评论