- 【模板】边双连通分量
a
- 2025-7-4 15:35:12 @
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5e5+2;
int n,m;
vector<int>g1[N];
int dfn[N],low[N],dfn_tot=0;
stack<int>stk;
int belong[N],ebcc_tot=0;
vector<int>ebcc[N];
void Tarjan(int u,int fa)
{
dfn[u]=low[u]=dfn_tot++;
stk.push(u);
bool flag=0;
for(auto v:g1[u])
{
if(v==u)continue;
if(!dfn[v])
Tarjan(v,u),low[u]=min(low[u],low[v]);
else if(v!=fa || flag)
low[u]=min(low[u],dfn[v]);
else flag=1;
}
if(dfn[u]==low[u])
{
ebcc_tot++;
int v;
do
{
v=stk.top(),stk.pop();
belong[v]=ebcc_tot;
ebcc[ebcc_tot].push_back(v);
}while(u!=v);
}
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;cin>>a>>b;
g1[a].push_back(b);
g1[b].push_back(a);
}
for(int i=1;i<=n;i++)
if(!dfn[i])Tarjan(i,0);
cout<<ebcc_tot<<"\n";
for(int i=1;i<=ebcc_tot;i++,cout<<"\n")
{
cout<<ebcc[i].size()<<" ";
for(auto j:ebcc[i])
cout<<j<<" ";
}
return 0;
}
0 comments
No comments so far...
Information
- ID
- 415
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 60
- Accepted
- 14
- Uploaded By