75分求助

P8436 【模板】边双连通分量

Lyy450605 @ 2023-08-10 22:00:52

求调试,最后两个点 \color{red}{WA} ,显示连通分量数比答案大一千左右。qwq ,玄关

#include <bits/stdc++.h>
#define Lon long long
using namespace std;

const int N=1e6+10;
const int M=2e6+10;
const int INF=0x3f3f3f3f;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

struct LINK{//结构体
    struct Node{
        int to;
        int next;
    };
    Node edge[M<<1]; int head[N],cnt;
    LINK (){//构造函数
        cnt=1;//用异或
    }
    inline void Insert(int from,int to){
        ++cnt;
        edge[cnt].to=to;
        edge[cnt].next=head[from]; head[from]=cnt;
    }
};

int n,m,a,b;  LINK G;
int low[N],dfn[N],dfcnt; bitset<M> vis1; bitset<N> vis2;
vector<int> ans[N];  int dcc;

void tarjen(int cur,int last){
    dfn[cur]=low[cur]=++dfcnt;
    for(int i=G.head[cur];i;i=G.edge[i].next){
        int to=G.edge[i].to;
        if(to==last) continue;//
        if(!dfn[to]){
            tarjen(to,cur);
            low[cur]=min(low[cur],low[to]);
            if(low[to]>dfn[cur]){//
                vis1[i]=1;
                vis1[i^1]=1;
            }
        }
        else low[cur]=min(low[cur],dfn[to]);
    }
}
void dfs(int cur,int last){
    vis2[cur]=1;
    ans[dcc].push_back(cur);
    for(int i=G.head[cur];i;i=G.edge[i].next){
        int to=G.edge[i].to;
        if(vis2[to]||vis1[i]) continue;
        dfs(to,cur);
    }
}

signed main(){//想法:删除桥
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        if(a==b) continue;
        G.Insert(a,b);
        G.Insert(b,a);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjen(i,0);
        }
    }
    for(int i=1;i<=n;i++){
        if(!vis2[i]){
            dcc++;
            dfs(i,0);
        }
    }
    cout<<dcc<<"\n";
    for(int i=1;i<=dcc;i++){
        cout<<ans[i].size()<<" ";
        for(int j=0;j<ans[i].size();j++) cout<<ans[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}

by Lyy450605 @ 2023-08-11 08:23:06

捞,求调试qwq


by Lyy450605 @ 2023-08-11 08:34:19

???

我把空间开到

const int N=2e6+10;
const int M=4e6+10;
然后过了

by wangyang0222 @ 2023-08-11 14:13:50

%%%


by Nwayy @ 2023-08-26 10:16:03

@Lyy450605 因为你要存双向边,空间必须开到两倍。


|