开快读全T,用cin全RE,但是过样例,

P8436 【模板】边双连通分量

apple_vinegar @ 2024-08-12 11:44:08

甚至下载的测试点也是秒过 输入 4 3 1 2 4 2 2 2 输出 4 1 1 1 2 1 3 1 4

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5,M=5e5+5;
int e[N],ne[N],h[N],idx=2,dfn[M],low[M],cnt,vis[M],num,n,m;
bool bz[N*2];
vector <int>ans[N*2];
int add(int a,int b){
    e[idx] =b;
    ne[idx]=h[a];
    h[a]=idx++;
}

void tarjan(int u,int fa){
    dfn[u]=low[u]=++cnt;
    for(int i=h[u];i;i=ne[i]){
        int v=e[i];
        if(dfn[v]==0){
            tarjan(v,i);
            if(dfn[u]<low[v]) bz[i]=bz[i^1]=1;
            low[u]=min(low[u],low[v]);
        }
        else if(i!=(fa^1)){ 
            low[u]=min(low[u],dfn[v]);
        }

    }
}

void dfs(int u,int id){
    vis[u]=id,ans[id-1].push_back(u);
    for(int i=h[u];i;i=ne[i]){
        int v=e[i];

        if(vis[v] || bz[i])continue;
        dfs(v,id); 
    }
}

int read(){
    int a=1,b=0;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-'){
            a=-a;ch=getchar();
        }       
    }
    while(ch>='0' && ch<='9'){
        b=(b<<1)+(b<<3)+(ch^48);
        ch=getchar();
    }
    return b;
}

int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int u,v;
        u=read(),v=read();
        if(u==v) continue;
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i,0);
    }
//  for(int i=1;i<=n;i++)cout<<dfn[i]<<" "<<low[i]<<endl;
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            dfs(i,++num);
        }
    }
    printf("%d\n",num);
    for(int i=0;i<num;i++){
        printf("%d",ans[i].size());
        for(int j=0;j<ans[i].size();j++) printf(" %d",ans[i][j]);
        printf("\n");
    }
    return 0;
}

by yx666 @ 2024-08-12 11:47:24

@penggc16801 add 没返回值


by apple_vinegar @ 2024-08-12 11:50:44

@yx666 多谢,但是为什么快读会T啊


by yx666 @ 2024-08-12 11:59:15

@penggc16801 快读打错了

要把第一个 while 改成

while(ch<'0' || ch>'9'){
        if(ch=='-')
            a=-a;
        ch=getchar();       
    }

|