Tarjan

强连通分量

vector<int> dfn(n + 1), low(n + 1), f(n + 1);
int dfncnt = 0, flag = 0;
stack<int> st;
auto tarjan = [&](auto self, int u) -> void {
    dfn[u] = low[u] = ++dfncnt;
    st.push(u);

    for (auto v : e[u]) {
        if (!dfn[v]) {
            self(self, v);
            low[u] = min(low[u], low[v]);
        }
        else if (f[v] == 0) {
            low[u] = min(low[u], low[v]);
        }
    }

    if (dfn[u] == low[u]) {
        ++flag;
        while (st.top() != u) {
            f[st.top()] = flag;
            st.pop();
        }
        st.pop();
        f[u] = flag;
    }
};
for (int i = 1; i <= n; i++) {
    if (dfn[i] == 0) {
        tarjan(tarjan, i);
    }
}

求割点

vector<int> dfn(n + 1), low(n + 1), cut(n + 1);
int dfncnt = 0;
int start = 0;

auto tarjan = [&](auto self, int u) -> void {
    dfn[u] = low[u] = ++dfncnt;
    int child = 0;

    for (auto v : e[u]) {
        if (!dfn[v]) {
            child++;
            self(self, v);
            low[u] = min(low[u], low[v]);

            if (low[v] >= dfn[u] && !cut[u]) {
                if (u != start || child >= 2) {
                    cut[u] = 1;
                }
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
};

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

只要有一个孩子回不到原来的点（也就是low[v] 》 dfn[u] ，那么这个点就是割点，注意如果是起点要额外加上有两个儿子这个条件

割边

点双连通分量

在一张连通的无向图中，对于两个点和，如果无论删去哪个点（只能删去一个）都不能使它们不连通，我们就说和 点双连通

边双连通分量

在一张连通的无向图中，对于两个点和，如果无论删去哪条边（只能删去一个，且不能删和自己）都不能使它们不连通，我们就说和 边双连通

性质：

边双连通具有传递性，即，若x , y 边双连通，y, z 边双连通，则 x , z 边双连通。
点双连通不具有传递性。

边双缩点：边双树

就像强联通分量缩点一样，我们可以把每一个边双缩成一个点来处理一些问题，然后这些点之间由原来的割边相连形成了一棵树。

最后得出一定是一棵树（森林），如果不是树，那就有环，环就是个边双。

就像强连通分量分解把一般有向图变成了有向无环图一样，我们把无向图的问题转到了树上，更好处理了，同时也保存了原来无向图的信息。

vector<int> dfn(n + 1), low(n + 1), f(n + 1);
int dfncnt = 0, flag = 0;
vector<int> bridge(n + 1);
stack<int> stk;
vector<vector<int>> ans;

auto tarjan = [&](auto self, int u, int fa) -> void {
    dfn[u] = low[u] = ++dfncnt;
    stk.push(u);

    int lin = 0;
    for (auto v : e[u]) {
        if (v == fa) {
            lin++; if (lin == 1) continue;
        }
        if (!dfn[v]) {
            self(self, v, u);
            low[u] = min(low[u], low[v]);
        }
        else {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (low[u] == dfn[u]) {
        ++flag;
        vector<int> g;
        while (stk.top() != u) {
            f[stk.top()] = flag;
            g.push_back(stk.top());
            stk.pop();
        }
        g.push_back(stk.top());
        stk.pop();
        f[u] = flag;
        ans.push_back(g);
    }
};

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

把边缩掉之后图会变成一颗树，那么在这之上的操作性质会更好

强连通分量

求割点

割边

点双连通分量

边双连通分量

边双缩点：边双树