algo-aha

tarjan算法找桥

• https://leetcode.com/problems/critical-connections-in-a-network/

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
    // 不在环上就是关键连接（桥）
    vector<vector<int>> graph(n);
    for (const auto& edge : connections) {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }

    int time = -1; // 访问顺序计时
    vector<int> timestamp(n, -1); // 最初访问时给节点编号
    vector<int> lowlink(n, -1);   // 能访问到最早的非父节点

    vector<vector<int>> ans;
    function<void(int,int)> dfs = [&](int u, int parent) {
        timestamp[u] = lowlink[u] = ++time;
        for (int v : graph[u]) {
            if (v == parent) continue;
            if (timestamp[v] == -1) { // 子节点未访问
                dfs(v, u);
                lowlink[u] = min(lowlink[u], lowlink[v]);
                // bridge：子节点能访问到的最早非父节点 > 父节点
                if (lowlink[v] > timestamp[u]) ans.push_back({u, v});
            } else { // 子节点其实是递归树中的祖先节点
                lowlink[u] = min(lowlink[u], timestamp[v]);
            }
        }
    };

    for (int i = 0; i < n; i++) {
        if (timestamp[i] == -1) 
            dfs(i, -1);
    }
    return ans;
}