社区讨论
求条
P8436【模板】边双连通分量参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @miihp0to
- 此快照首次捕获于
- 2025/11/28 14:36 3 个月前
- 此快照最后确认于
- 2025/11/29 14:50 3 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
int next,to;
}e[80005];
int n,d[15005],l[15005],sjz,h[15005],cnt1,fa[15005],ans,m,a[1005][1005];
void add(int x,int y){
e[++cnt1]={h[x],y};
h[x]=cnt1;
}
void tarjan(int x){
l[x]=d[x]=++sjz;
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(fa[x]!=y){
if(d[y]==0){
fa[y]=x;
tarjan(y);
l[x]=min(l[x],l[y]);
if(l[y]>d[x])
ans++;
a[ans][++a[ans][0]]=y;
}
else
l[x]=min(l[x],d[y]);
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++)
if(d[i]==0){
ans++;
a[ans][++a[ans][0]]=i;
tarjan(i);
}
cout<<ans<<"\n";
for(int i=1;i<=ans;i++){
cout<<a[i][0];
for(int j=1;j<=a[i][0];j++)
cout<<" "<<a[i][j];
cout<<"\n";
}
return 0;
}
样例3过不了
回复
共 3 条回复,欢迎继续交流。
正在加载回复...