咋题解区没有vector 找桥+dfs一遍的

HaneDaniko @ 2024-11-28 20:38:00

by SnowTrace @ 2024-11-28 20:41:56

我曾经这么写过，如果忘记这个咋做了就可以这样求吧，但是我觉得还是写标准做法短一点

by hzoi_Shadow @ 2024-11-28 20:55:04

@HaneDaniko 之前贺的 学校课件

by supermzc @ 2024-11-28 21:15:25

@HaneDanikoemm,虽然我不是 vector存桥，用的bool数组标记，但我是dfs一遍找的。

码风很丑见谅

#include<bits/stdc++.h>
#define fir first 
#define sec second 
using namespace std;
struct node{
    int v,nxt;
};
const int MAXN=6e5+7,MAXM=2e6+7;
node mar[MAXM*2];
int tp[MAXN],mp=1;
void add(int a,int b){
    mar[++mp].v=b;
    mar[mp].nxt=tp[a];
    tp[a]=mp;
}
bool cut[MAXM*2];
int dfn[MAXN],low[MAXN],tk=0;
void tarjan(int pos,int fa){
    dfn[pos]=low[pos]=++tk;
    int v;
    for(int i=tp[pos];i!=0;i=mar[i].nxt){
        v=mar[i].v;
        if(!dfn[v]){
            tarjan(v,i);
            if(low[v]>dfn[pos]){
                cut[i]=1;
                cut[i^1]=1;
            }
            low[pos]=min(low[pos],low[v]);
        }
        else if(i!=(fa^1))low[pos]=min(low[pos],dfn[v]);
    }
}
int col[MAXN],tc=0;
vector<int> ans[MAXN];
void dfs(int pos,int color){
    col[pos]=color;
    ans[color].push_back(pos);
    for(int i=tp[pos];i!=0;i=mar[i].nxt){
        if(col[mar[i].v]==0&&cut[i]==0){
            dfs(mar[i].v,color);
        }
    }
}
int main(){
    int n,m,u,v;
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        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++){
        if(!col[i]){
            dfs(i,++tc);
        }
    }
    cout<<tc<<'\n';
    for(int i=1;i<=tc;i++){
        cout<<ans[i].size()<<' ';
        for(auto j:ans[i])cout<<j<<' ';
        cout<<'\n';
    }
}

by HaneDaniko @ 2024-11-28 21:19:30

调出来了，挂着给大家参考吧

https://www.luogu.com.cn/paste/56oa1frv

by Fish_ht @ 2024-12-08 13:37:56

@HaneDaniko thx,造福后人啊啊啊啊啊啊。