全TLE求条

P8436 【模板】边双连通分量

shenyibo12200 @ 2025-01-10 16:12:04


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MANX=2000010;
int tot=1,n,m;
int to[MANX],nxt[MANX],head[MANX];
int dfn[MANX],low[MANX],times;
bool bridge[MANX];
int id[MANX],dcc=0;
vector<int> d[MANX];
void add(int x,int y){
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
int tarjan(int x,int edge){
    dfn[x]=low[x]=++times;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(!dfn[y]){
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<low[y]){
                bridge[i]=bridge[i^1]=true;
            }
        }
        else if(i!=(edge^1)) low[x]=min(low[x],dfn[y]);
    }
}
void dfs(int x){
    id[x]=dcc;
    d[dcc].push_back(x);
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(id[y] || bridge[i]) continue;
        dfs(y);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        add(x,y); add(y,x);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i,0);
    }
    for(int i=1;i<=n;i++){
        if(!id[i]){
            dcc++;
            dfs(i);
        } 
    }
    cout<<dcc<<"\n";
    for(int i=1;i<=dcc;i++){
        int len=d[i].size();
        cout<<len<<" ";
        for(int j=0;j<len;j++){
            cout<<d[i][j]<<" "; 
        }
        cout<<"\n";
    }
    return 0;
}

by shenyibo12200 @ 2025-01-10 16:15:34

@Rubbish_Du

学长求助!


by Rubbish_Du @ 2025-01-10 16:16:06

先把tarjan函数的int改成void@shenyibo12200


by Rubbish_Du @ 2025-01-10 16:17:44

再把数组开大点,双向边,得开两倍@shenyibo12200


by Rubbish_Du @ 2025-01-10 16:19:10

然后没了@shenyibo12200


by shenyibo12200 @ 2025-01-10 16:25:43

@Rubbish_Du

我去感谢感谢(orz orz)


by furina_yyds @ 2025-01-10 16:29:04

@Rubbish_DuTa是谁啊


by furina_yyds @ 2025-01-10 16:29:30

太久没上都掉了


by Rubbish_Du @ 2025-01-10 16:29:46

@furina_yyds 学弟


by Rubbish_Du @ 2025-01-10 16:30:55

@furina_yyds?


|