求用vector的边双代码。

_JF_ @ 2023-05-27 13:43:11

by __vector__ @ 2023-05-27 13:49:28

vector 找反响边很麻烦，为啥要用 vector

by jijidawang @ 2023-05-27 14:39:37

const int N = 4e6 + 233;
int n, m, dfn[N], low[N], cc, edcc;
vector<int> dcc[N];
struct FutureGraph
{
    int id;
    vector<pii> g[N];
    inline void addedge(int u, int v){g[u].emplace_back(make_pair(id++, v));}
    inline void ade(int u, int v){addedge(u, v); addedge(v, u);}
    inline vector<pii> operator[](const int& id) const {return g[id];}
    inline vector<pii>& operator[](const int& id){return g[id];}
    inline static int rev(int id){return id ^ 1;}
    inline void clear(int n = N - 1){id = 0; for (int i=0; i<=n; i++) g[i].clear();}
    FutureGraph(){id = 0;}
}g;
void tarjan(int u, int eid)
{
    static stack<int> S;
    dfn[u] = low[u] = ++cc; S.push(u);
    for (pii e : g[u])
    {
        int id = e.first, v = e.second;
        if (id == FutureGraph :: rev(eid)) continue;
        if (dfn[v]) chkmin(low[u], dfn[v]);
        else {tarjan(v, id); chkmin(low[u], low[v]);}
    }
    if (low[u] >= dfn[u])
    {
        ++edcc; int z;
        do {dcc[edcc].emplace_back(z = S.top()); S.pop();} while (z != u);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i=0, u, v; i<m; i++){scanf("%d%d", &u, &v); g.ade(u, v);}
    for (int i=1; i<=n; i++)
        if (!dfn[i]) tarjan(i, -1);
    printf("%d\n", edcc);
    for (int i=1; i<=edcc; i++)
    {
        printf("%lu", dcc[i].size());
        for (int x : dcc[i]) printf(" %d", x);
        puts("");
    }
    return 0;
}