奇怪的50pts

P8436 【模板】边双连通分量

CNS_5t0_0r2 @ 2023-11-16 10:19:41

https://www.luogu.com.cn/record/135330566

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 9,M = 2e6 + 9;
struct egde{
    int to,nex;
} e[M << 1];
int ecnt,head[N];
void addegde(int u,int v){
    ecnt++;
    e[ecnt] = (egde){v,head[u]};
    head[u] = ecnt;
}
int n,m,x,y;
int id,cnt,dfn[N],low[N];//id表示DFS序
vector<int> ans[N];//第i个连通分量的个点
stack<int>s;
void dfs(int cur,int father){//cur表示当前顶点,father表示其在生成树上的父节点
    id++;
    dfn[cur] = id;
    low[cur] = id;//当前顶点一定能回到自己。
    s.push(cur);
    for(int i = head[cur];i;i = e[i].nex){
        int v = e[i].to;
        if(!dfn[v]){//如果这个顶点未被遍历到,遍历它
            dfs(v,cur);
            low[cur] = min(low[cur],low[v]);
            //更新当前顶点能遍历到的最早dfn
        }
        else if(v != father)//否则如果顶点v被遍历过,并且不是cur的父节点,说明v是cur的非父祖先,因此可以不经过父节点到达它,更新当前节点能到的最小点的dfn
            low[cur] = min(low[cur],dfn[v]);
    }
    if(low[cur] == dfn[cur]){
        int v;
        cnt++;
        do{
            v = s.top();s.pop();
            ans[cnt].push_back(v);
        }while(v != cur);
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= m;i++){
        scanf("%d%d", &x, &y);
        addegde(x,y);
        addegde(y,x);
    }
    for(int i = 1;i <= n;i++)
        if(!dfn[i])
            dfs(i,0);
    printf("%d\n",cnt);
    for(int i = 1;i <= cnt;i++){
        int siz = ans[i].size();
        printf("%d ",siz);
        for(int j = 0;j < siz;j++)
            printf("%d ",ans[i][j]);
        printf("\n");
    }
    return 0;
}

by Genius_Star @ 2024-01-15 21:47:26

@5t0_0r2 可能有重边


|