本地RE,提交AC

P8436 【模板】边双连通分量

catandcode @ 2023-04-09 08:25:37

rt

#include<bits/stdc++.h>
#define ld long double
#define ll long long
using namespace std;
int cnt,tim,n,m,dfn[500005],low[500005],q[500005],tail;
vector<pair<int,int> > path[500005];
vector<int> dcc[500005];
void form(int now)
{
    ++cnt;
    int x;
    do
    {
        x=q[tail--];
        dcc[cnt].push_back(x);
    }while(x!=now);
}
void tarjan(int now,int num)
{
    q[++tail]=now,dfn[now]=low[now]=++tim;
    for(int i=0;i<path[now].size();++i)
    {
        if(path[now][i].second==num) continue;
        int nxt=path[now][i].first;
        if(!dfn[nxt])
        {
            tarjan(nxt,path[now][i].second);
            low[now]=min(low[now],low[nxt]);
            if(low[nxt]>dfn[now]) form(nxt);
        }
        else low[now]=min(low[now],dfn[nxt]);
    }
    if(!num) form(now);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int a,b;
        cin>>a>>b;
        path[a].push_back(make_pair(b,i));
        path[b].push_back(make_pair(a,i));
    }
    for(int i=1;i<=n;++i)
    {
        tail=0;
        if(!dfn[i])
            tarjan(i,0);
    }
    cout<<cnt<<endl;
    for(int i=1;i<=cnt;++i)
    {
        cout<<dcc[i].size()<<' ';
        for(int j=0;j<dcc[i].size();++j)
            cout<<dcc[i][j]<<' ';
        cout<<endl;
    }
    return 0;
}

by syta @ 2023-04-09 09:04:48

本地开无限栈了吗(


by catandcode @ 2023-04-09 15:09:21

@syta ?您的意思是什么?没太理解。


by catandcode @ 2023-04-09 15:30:47

@syta 去搜了一下,解决了,谢谢您。


by syta @ 2023-04-09 15:41:18

@catandcode 不用谢捏!~


|