开 O2 就 RE?

P8436 【模板】边双连通分量

qwq___qaq @ 2023-04-01 11:14:44

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+5;
int n,m,tot,u[maxn],v[maxn],dfn[maxn],low[maxn],fa[maxn];
inline int Make(int n){
    for(int i=1;i<=n;++i)
        fa[i]=i;
}
int Find(int x){
    return fa[x]=(x==fa[x]?x:Find(fa[x]));
}
bool flg[maxn]; 
struct edge{
    int to,id;
};
vector<edge> G[maxn];
vector<int> g[maxn];
void Tarjan(int u,int fa){
    low[u]=dfn[u]=++tot;
    for(auto N:G[u]){
        int v=N.to,id=N.id;
        if(v==fa)
            continue;
        if(!dfn[v]){
            Tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<low[v])
                flg[id]=1;
        } else if(v!=fa)
            low[u]=min(low[u],dfn[v]);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&u[i],&v[i]);
        G[u[i]].push_back(edge({v[i],i}));
        G[v[i]].push_back(edge({u[i],i}));
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i])
            Tarjan(i,0);
    Make(n);
    for(int i=1;i<=m;++i)
        if(!flg[i])
            fa[Find(u[i])]=Find(v[i]);
    int cnt=0;
    for(int i=1;i<=n;++i){
        cnt+=(fa[i]==i);
        g[Find(i)].push_back(i);
    }
    printf("%d\n",cnt);
    for(int i=1;i<=n;++i)
        if(Find(i)==i){
            printf("%d",int(g[i].size()));
            for(auto v:g[i])
                printf(" %d",v);
            puts("");
        }
    return 0;
}

by liangbowen @ 2023-04-01 11:27:43

@UnnamedOrNamed 改 void Make(int n)


by Sprague_Garundy @ 2023-04-01 13:40:36

@UnnamedOrNamed 非 void 函数无返回值是 UB,开 O2 后就会 RE。


|