关于一种特殊写法

P8436 【模板】边双连通分量

Zi_Gao @ 2023-07-30 09:16:37

#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE int
INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){register char s[20];register int i=0;if(x<0){x=-x;putchar('-');}if(x==0){putchar('0');return;}while(x){s[i++]=x%10;x/=10;}while(i){putchar(s[--i]+'0');}return;}

struct EDGE{
    int v,id;
};

std::vector<EDGE> e[500010];
std::vector<int> edcc[500010];
std::stack<int> stack;

int dfn[500010],low[500010],cnt,tot;
char isEdcc[2000010],vis[500010];

void addEdge(int u,int v,int id){
    e[u].push_back(EDGE{v,id});
    return;
}

void tarjan(int u,int p){
    // print(u);putchar(' ');
    low[u]=dfn[u]=(dfn[p]+1);
    stack.push(u);
    for(auto edge:e[u])
        if(edge.v!=p){
            if(dfn[edge.v]&&edge.v!=p) low[u]=std::min(low[u],dfn[edge.v]);
            else{
                tarjan(edge.v,u);
                if(low[edge.v]>dfn[u]) isEdcc[edge.id]=1;
                low[u]=std::min(low[u],low[edge.v]);
            }
        }
    return;
}

void dfs(int u){
    vis[u]=1;
    edcc[cnt].push_back(u);
    for(auto edge:e[u])
        if(!vis[edge.v]&&!isEdcc[edge.id])
            dfs(edge.v);
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("name.in", "r", stdin);
    freopen("name.out", "w", stdout);
    #endif

    register int i,u,v;
    int n=read();
    int m=read();

    for(i=0;i<m;++i){
        u=read();
        v=read();
        if(u==v) continue;
        addEdge(u,v,i);
        addEdge(v,u,i);
    }

    for(i=1;i<=n;++i)
        if(!dfn[i])
            tarjan(i,i);

    for(i=1;i<=n;++i)
        if(!vis[i]){
            dfs(i);
            ++cnt;
        }

    print(cnt);putchar('\n');
    for(i=0;i<cnt;++i){
        print(edcc[i].size());putchar(' ');
        for(auto u:edcc[i]){
            print(u);putchar(' ');
        }
        putchar('\n');
    }

    #ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    #endif
    return 0;
}

这份代码中并没有记录来时的边,只传入了父亲,但是还是可以跑对,不知道有没有可以卡的方法。


by Nuclear_Pasta @ 2023-07-30 09:22:48

@Zi_Gao

input:
3 3
1 2
2 1
1 3
output:
2
2 1 2
1 3

by Zi_Gao @ 2023-07-30 09:25:25

@departure2020 似乎并没有卡掉


by Nuclear_Pasta @ 2023-07-30 09:32:44

@Zi_Gao

input:
4 5
1 2
2 3
3 2
3 4
1 4
output:
3
1 1
2 2 3
1 4

by Zi_Gao @ 2023-07-30 09:36:56

@departure2020 您给出的output正确吗?我拿题解跑是

1
4 1 4 3 2

和我的一样


by Nuclear_Pasta @ 2023-07-30 09:40:45

@Zi_Gao 抱歉,output错了,重新出一个。

input:
4 4
1 2
2 3
3 2
3 4
output:
3
1 1
2 2 3
1 4

by Zi_Gao @ 2023-07-30 09:44:16

@departure2020 很遗憾并没有卡掉


by zzk2010 @ 2023-07-31 10:03:50

@Zi_Gao 看看这个

个人认为传父亲也是可以的。题解区代码大多用的是链式前向星,所以记录边更方便。两者本质都是为了不走回头路吧。


by Zi_Gao @ 2023-07-31 10:56:17

@zzk2010 ok


|