C++的算法：割点与割边

        在图论中，割点与割边是图的重要性质，它们在图的连通性、网络流等问题中扮演着关键角色。在C++中，我们可以通过深度优先搜索（DFS）等算法来判定一个图中的割点与割边。

        割点，又称关节点或桥接点，是指在无向连通图中，如果删除某个顶点后，图的连通分量数增加，则称该顶点为割点。

        判定割点的一个常用方法是Tarjan算法。该算法在深度优先搜索的过程中，维护了一个时间戳和一个低值（low）数组。时间戳记录了节点被访问的顺序，而low数组则记录了节点及其子树中能够回溯到的最早访问时间。

        在DFS过程中，对于当前节点u，我们遍历其所有邻接节点v。若v是u的一个未被访问过的邻接节点，我们继续递归访问v，并更新u的low值为min(low[u], low[v])。若v是u的一个已访问过的邻接节点，并且v不是u的父节点（避免回溯到父节点造成的错误更新），我们也更新u的low值为min(low[u], dfn[v])，其中dfn数组存储的是节点的访问时间戳。

        若对于节点u，存在至少一个邻接节点v，使得low[v] >= dfn[u]，则说明从v及其子树中无法回溯到u的父节点或更早的节点，因此u是一个割点。

        示例为寻找割点，代码如下。

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

const int MAXN = 1005; // 假设最大节点数为1000
vector<int> adj[MAXN]; // 邻接表存储图
int dfn[MAXN], low[MAXN], index; // 时间戳和最低时间戳
bool isArticulation[MAXN]; // 标记是否为割点

void dfs(int u, int parent) {
    dfn[u] = low[u] = ++index;
    int children = 0; // 统计子节点数量
    for (int v : adj[u]) {
        if (!dfn[v]) { // 如果v未被访问过
            children++;
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (parent != -1 && low[v] >= dfn[u]) {
                isArticulation[u] = true; // u是割点
            }
        } else if (v != parent) { // 如果v已被访问过且不是u的父节点
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (parent == -1 && children > 1) { // 根节点且有多于一个子节点时也是割点
        isArticulation[u] = true;
    }
}

void findArticulationPoints(int root, int n) {
    index = 0;
    fill(dfn, dfn + n, 0);
    fill(low, low + n, 0);
    fill(isArticulation, isArticulation + n, false);
    dfs(root, -1); // 从根节点开始DFS
}

int main() {
    // 构建图
    int n, m; // n为节点数，m为边数
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); // 无向图，需要添加双向边
    }

    // 查找割点
    findArticulationPoints(1, n); // 假设根节点为1
    cout << "Articulation points: ";
    for (int i = 1; i <= n; ++i) {
        if (isArticulation[i]) {
            cout << i << " ";
        }
    }
    cout << endl;

    return 0;
}

        割边，又称桥，是指在无向连通图中，如果删除某条边后，图的连通分量数增加，则称该边为割边。

        割边的判定也可以在深度优先搜索的过程中完成。当我们访问到一个新的节点v时，如果它的low值大于它的父节点u的dfn值，则说明从v及其子树中无法回溯到u的其他邻接节点，因此u和v之间的边就是一条割边。

        以下是割边判定的示例代码。

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

const int MAXN = 1005;
vector<pair<int, int>> adj[MAXN]; // 邻接表存储图，记录边的信息
int dfn[MAXN], index; // 时间戳
bool isBridge[MAXN << 1]; // 标记是否为割边，数组大小为边的两倍，因为每条边需要两个位置的标记


void dfs(int u, int parentEdge) {
    dfn[u] = ++index;
    for (const auto& edge : adj[u]) {
        int v = edge.first, id = edge.second;
        int edgeToParent = (v == parentEdge / 2 + 1) ? parentEdge : -1; // 判断是否是回溯到父节点的边
        if (!dfn[v]) {
            dfs(v, edgeToParent);
            if (dfn[u] < dfn[v]) { // (u, v) 是割边
                isBridge[id] = isBridge[id ^ 1] = true;
            }
        }
    }
}
void findBridges() {
    index = 0;
    fill(dfn, dfn + MAXN, 0);
    fill(isBridge, isBridge + MAXN * 2, false);
    dfs(1, -1); // 从节点1开始DFS，-1表示没有父边
}

int main() {
    // 构建图的示例（与前面割点判定使用相同的图）
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i * 2}); // 记录边的信息，每条边在数组中有两个位置
        adj[v].push_back({u, i * 2 + 1});
    }

    findBridges(); 
    cout << "Bridges: ";
    for (int u = 1; u <= n; ++u) {
        for (int i = 0; i < m * 2; i += 2) {
            if (isBridge[i] || isBridge[i + 1]) { // 判断是否为割边
            cout << "(" << adj[adj[i / 2].first][i / 2].first << ", "
                 << adj[adj[i / 2].first][i / 2].second << ") ";
        }
        }
    }
    cout << endl;

    return 0;
}

        割点与割边的概念在许多图论算法和网络分析中具有重要应用。例如，在网络可靠性分析中，通过识别割点和割边，我们可以确定网络的脆弱部分，以便进行有针对性的加固。另外，在图的最小割和最大流问题中，也常常利用割边的性质来求解。

        在实际应用中，你可能需要根据具体的业务需求调整图的构建方式，例如使用邻接矩阵代替邻接表，或者处理有向图的情况。但是，无论图的表示方式如何变化，割点与割边的判定方法都是基于深度优先搜索的。