P8436 【模板】边双连通分量

~~~~~      P8436 【模板】边双连通分量 ~~~~~      总题单

讲解

~~~~~      什么是边双连通分量？就是不包含割边的极大连通块。

~~~~~      怎么找边双连通分量？就是割边的时候将遍历到的点放到一个桶里，若当前边是割边，则在桶内且时间戳大于等于当前点的时间戳的点就是一个边双连通分量。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;ll head[4000005],egt=1;
struct Edge{ll v,nxt;}eg[4000005];
inline void adeg(ll u,ll v){eg[++egt]={v,head[u]};head[u]=egt;
}ll n,m,tot,cnt;
ll top,stk[500005];
vector<ll>pot[500005];
vector<pair<ll,ll>>bir;
ll dfn[500005],low[500005];void Tarjan(ll p,ll ineg){dfn[p]=low[p]=++tot;stk[++top]=p;for(ll i=head[p];i;i=eg[i].nxt){ll v=eg[i].v;if(!dfn[v]){Tarjan(v,i);low[p]=min(low[p],low[v]);if(low[p]>dfn[p])bir.push_back({p,v});}else if(i!=(ineg^1))low[p]=min(low[p],dfn[v]);}if(low[p]==dfn[p]){//重点 cnt++;while(top>=1){ll v=stk[top--];pot[cnt].push_back(v);if(v==p)break;}}
}signed main(){ios::sync_with_stdio(false);cin>>n>>m;while(m--){ll x,y;cin>>x>>y;adeg(x,y);adeg(y,x);}for(ll i=1;i<=n;i++)if(!dfn[i])Tarjan(i,0);cout<<cnt<<endl;for(ll i=1;i<=cnt;i++){cout<<pot[i].size()<<" ";for(ll it:pot[i])cout<<it<<" ";cout<<endl;}return 0;
}

~~~~~      引用请附名 $——$ OMG_NOIP