求无向图的边双连通分量（即在分量中删去任何一条边这个分量依然连通）

undirected_tarjan.cpp

int clk, dfu[maxn], low[maxn], sz, belong[maxn];
bool inStack[maxn];
std::stack<int> st;
std::vector<std::vector<int> > comp;

void tarjan(int u, int fa) {
    dfu[u] = low[u] = ++clk;
    st.push(u);
    inStack[u] = true;
    for (int v: g[u]) {
        if (v == fa) continue;
        if (!dfu[v]) {
            tarjan(v, u);
            low[u] = std::min(low[u], low[v]);
        } else {
            low[u] = std::min(low[u], dfu[v]);
        }
    }
    if (dfu[u] == low[u]) {
        std::vector<int> v;
        sz++;
        while (true) {
            int hd = st.top();
            st.pop();
            inStack[hd] = false;
            v.pb(hd);
            belong[hd] = sz;
            if (hd == u) break;
        }
        comp.pb(v);
    }
}