在图论中，特别是在讨论有向图（Directed Graph）时，我们常常需要了解图的结构特性，比如强联通分量（Strongly Connected Components, SCC）。了解强联通分量中的各种边对于理解图的整体结构以及某些算法（如Tarjan's算法或Kosaraju's算法）是非常重要的。以下是对强联通分量及其边类型的解释：
强联通分量（SCC）
强联通分量是一个子图，其中每对顶点之间都有路径相互可达。换句话说，一个强联通分量内的任意两个顶点 u 和 v 都满足 u 到 v 和 v 到 u 之间存在路径。
边的分类
板子如下
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> e[N]; // 存储图的邻接表
int dfn[N], low[N]; // 存储每个节点的时间戳和最小到达时间
bool ins[N]; // 标记节点是否在栈中
int idx, bel[N], cnt; // 时间戳、节点所属的强联通分量编号、强联通分量计数
stack<int> stk; // 用于 Tarjan 算法的栈
vector<vector<int>> scc;// 存储所有的强联通分量
int n, m; // 节点数和边数void dfs(int u) {dfn[u] = low[u] = ++idx; // 初始化时间戳ins[u] = true; // 标记节点在栈中stk.push(u); // 将节点压入栈中for (auto v : e[u]) { // 遍历节点 u 的所有邻接点 vif (!dfn[v]) { // 如果节点 v 尚未访问dfs(v); // 递归访问节点 vlow[u] = min(low[u], low[v]); // 更新节点 u 的最小到达时间} else if (ins[v]) { // 如果节点 v 在栈中low[u] = min(low[u], dfn[v]); // 更新节点 u 的最小到达时间}}if (dfn[u] == low[u]) { // 如果节点 u 是强联通分量的根节点vector<int> c; // 创建一个新的强联通分量++cnt;while (1) {int v = stk.top(); // 弹出栈顶节点c.push_back(v); // 将节点添加到当前强联通分量中ins[v] = false; // 标记节点不在栈中bel[v] = cnt; // 标记节点所属的强联通分量编号stk.pop(); // 弹出栈顶节点if (u == v) break; // 如果节点 u 是栈顶节点，结束循环}sort(c.begin(), c.end()); // 对强联通分量内的节点排序scc.push_back(c); // 将强联通分量添加到结果中}
}int main() {ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; i++) {int u, v;cin >> u >> v;e[u].push_back(v); // 构建邻接表}for (int i = 1; i <= n; i++) {if (!dfn[i]) dfs(i); // 对每个未访问的节点进行 DFS}sort(scc.begin(), scc.end()); // 对所有的强联通分量排序cout << cnt << endl; // 输出强联通分量的数量for (auto c : scc) { // 输出每个强联通分量for (auto u : c) {cout << u << " ";}cout << endl;}return 0;
}
题目链接 洛谷 B3609
参考文献 scc