50分求助

P8436 【模板】边双连通分量

DLYdly2010 @ 2023-01-15 22:06:20

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,M=2e6+10;
vector<int>a[N],ans[N];
int n,m,cnt,tot,top,st[N],dfn[N],low[N];
void Tarjan(int u,int fa)
{
    dfn[u]=low[u]=++tot,st[++top]=u;
    for(int i=0;i<a[u].size();i++)
    {
        int v=a[u][i];
        if(v==fa)continue;
        if(dfn[v]==0)
        {
            Tarjan(v,u);
            low[u]=min(low[u],low[v]);
        }
        else low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u])
    {
        cnt++;
        for(;st[top]!=u;top--)
        {
            ans[cnt].push_back(st[top]);
        }
        ans[cnt].push_back(u);
        top--;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])Tarjan(i,0);
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;i++)
    {
        printf("%d ",ans[i].size());
        for(int j=0;j<ans[i].size();j++)
        {
            printf("%d ",ans[i][j]);
        }
        printf("\n");
    }
    return 0;
}

|