一个疑问

P8436 【模板】边双连通分量

违规用户名690561 @ 2024-10-19 11:20:38

我仿照题解2写的

#include<bits/stdc++.h>
using namespace std;
int n, m, s1, s2;
int dfn[2000005], low[2000005], tot, len;
vector<pair<int, int>> e[2000005];
vector<int> v;
vector<vector<int>> ans;
stack<int> st;
void tarjan(int u, int las) {
    dfn[u] = low[u] = ++tot;
    st.push(u);
    for(auto i : e[u]) {
        int v = i.first;
        if(i.second == (las ^ 1)) {
            continue;
        }
        if(dfn[v] == 0) {
            tarjan(v, i.second);
            low[u] = min(low[u], low[v]);
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u]){
        v.clear();
        v.push_back(u);
        while(st.top() != u){
            v.push_back(st.top());
            st.pop();
        }
        st.pop();
        ans.push_back(v);
    }
    return;
}
int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d %d", &s1, &s2);
        e[s1].push_back({s2, i << 1});
        e[s2].push_back({s1, i << 1 | 1});
    }
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) {
            tarjan(i, 0);
        }
    }
    printf("%d\n", (int)ans.size());
    for(auto i : ans){
        printf("%d ", (int)i.size());
        for(auto j : i){
            printf("%d ", j);
        }
        printf("\n");
    }
    return 0;
}

一个疑问:为什么tarjan函数写得如此简单(甚至比别的tarjan算法都简单)就能求出边双?


by Melo_DDD @ 2024-10-19 11:29:34

@tzxxzt 建议学习 tarjan 算法


by 违规用户名690561 @ 2024-10-19 11:54:35

@Melo_DDD 。。。


|