强联通分量和tarjan

强连通分量（SCC）

dfs往下搜索，如果一块区域既不能往上连，也不能往前连，就是一个强连通分量，切掉。

强连通分量

vector<int> e[N];
int dfn[N], low[N], bel[N], ins[N], idx, cnt, n, m;//dfn表示dfs遍历到的顺序，low表示能够回溯到的最早的位置，ins表示该点是否已经被割掉，bel表示属于哪个连通块
stack<int> stk;
vector<vector<int>> scc;
void dfs(int u) {
    dfn[u] = low[u] = ++idx;
    ins[u] = true;
    stk.push(u);
     for (auto v : e[u]) {
         if (!dfn[v]) {
             dfs(v);
             low[u]=min(low[u],low[v]);
         }
         else {
             if(ins[v]) low[u]=min(low[u],dfn[v]);
         }
     }
    /*for (auto v : e[u]) {
        if (!dfn[v])
            dfs(v);
        if (ins[v])
            low[u] = min(low[u], low[v]);
    }*/
    if (dfn[u] == low[u]) {
        vector<int> c;
        ++cnt;
        while (true) {
            int v = stk.top();
            c.push_back(v);
            ins[v] = false;
            bel[v] = cnt;
            stk.pop();
            if (u == v)
                break;
        }
        sort(c.begin(), c.end());
        scc.push_back(c);
    }
}
void solve() {
    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);
    }
    sort(scc.begin(), scc.end());
    for (auto c : scc) {
        for (auto u : c) {
            cout << u << " ";
        }
        cout << endl;
    }
}

以下数据为上图，图中各个节点均+1

15 22
1 2
2 4
2 5
2 9
2 6
4 3
3 7
7 3
7 4
5 8
8 5
8 9
6 12
12 16
6 16
16 14
14 6
16 13
13 15
15 16
16 10
8 7

Tarjan

int n, m, cnt = 0;
int dfn[200020];
int low[200020];
stack<int>s;
bool vis[200020];
vector<int>edge[200020];
​
void tarjan(int now)
{
    dfn[now] = low[now] = ++cnt;
    s.push(now);
    vis[now] = 1;//表示该点是否入栈
    for (auto it:edge[now])
        if (!dfn[it])
        {
            tarjan(it);
            low[now] = min(low[now], low[it]);
        }
        else if (vis[it])
            low[now] = min(low[now], dfn[it]);
    int cur;
    if (dfn[now] == low[now]){
        do{
            cur = s.top();
            s.pop();
            vis[cur] = false;
            printf("%d ", cur);
        } while (now != cur);
        printf("\n");
    }
}
​
void solve()
{
    n = read();
    m = read();
    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        x = read();
        y = read();
        edge[x].push_back(y);
    }
    for (int i = 1; i <= n; ++i)
        if (!dfn[i]) tarjan(i);
}

点双连通

边双连通