0pts求调

P8436 【模板】边双连通分量

_Kamisato_Ayaka_ @ 2024-11-12 16:58:04

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e6 + 10;
int n,m,idx = 1,head[MAXN << 1],cur;
int low[MAXN],dfn[MAXN],color[MAXN],sccnt;
bool vis[MAXN];
stack < int > st;
vector < int > Ans[MAXN];
struct node{
    int v,nxt;
}edge[MAXN << 1];
inline void add(int u,int v)
{
    edge[idx].v = v;
    edge[idx].nxt = head[u];
    head[u] = idx ++;
}
inline void tarjan(int u,int fa)
{
    low[u] = dfn[u] = ++ cur;
    vis[u] = 1;
    st.push(u);
    for(int i = head[u];i != -1;i = edge[i].nxt)
    {
        int v = edge[i].v;
        if(i == (fa ^ 1)) continue;
        if(!dfn[v])
        {
            tarjan(v,i);
            low[u] = min(low[u],low[v]);
        }
        else if(vis[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        sccnt ++;
        while(st.top() != u)
        {
            color[st.top()] = sccnt;
            vis[st.top()] = 0;
            Ans[sccnt].push_back(tmp);
            st.pop();
        }
        st.pop();
    }
}
signed main()
{
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    memset(head,-1,sizeof(head));
    for(int i = 1;i <= m;i ++)
    {
        int u,v;
        cin >> u >> v;
        if(u != v) add(u,v),add(v,u);
    }
    for(int i = 1;i <= n;i ++)
    {
        if(!dfn[i]) tarjan(i,0);
    }
    cout << sccnt << endl;
    for(int i = 1;i <= sccnt;i ++)
    {
        cout << Ans[i].size() << " ";
        for(int j = 0;j < Ans[i].size();j ++)
            cout << Ans[i][j] << " ";
        cout << endl;
    }
    return 0;
}

|