shenyibo12200 @ 2025-01-10 16:12:04
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MANX=2000010;
int tot=1,n,m;
int to[MANX],nxt[MANX],head[MANX];
int dfn[MANX],low[MANX],times;
bool bridge[MANX];
int id[MANX],dcc=0;
vector<int> d[MANX];
void add(int x,int y){
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
int tarjan(int x,int edge){
dfn[x]=low[x]=++times;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(!dfn[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(dfn[x]<low[y]){
bridge[i]=bridge[i^1]=true;
}
}
else if(i!=(edge^1)) low[x]=min(low[x],dfn[y]);
}
}
void dfs(int x){
id[x]=dcc;
d[dcc].push_back(x);
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(id[y] || bridge[i]) continue;
dfs(y);
}
}
int main(){
ios::sync_with_stdio(false);
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(!dfn[i]) tarjan(i,0);
}
for(int i=1;i<=n;i++){
if(!id[i]){
dcc++;
dfs(i);
}
}
cout<<dcc<<"\n";
for(int i=1;i<=dcc;i++){
int len=d[i].size();
cout<<len<<" ";
for(int j=0;j<len;j++){
cout<<d[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
by shenyibo12200 @ 2025-01-10 16:15:34
@Rubbish_Du
学长求助!
by Rubbish_Du @ 2025-01-10 16:16:06
先把tarjan函数的int改成void@shenyibo12200
by Rubbish_Du @ 2025-01-10 16:17:44
再把数组开大点,双向边,得开两倍@shenyibo12200
by Rubbish_Du @ 2025-01-10 16:19:10
然后没了@shenyibo12200
by shenyibo12200 @ 2025-01-10 16:25:43
@Rubbish_Du
我去感谢感谢(orz orz)
by furina_yyds @ 2025-01-10 16:29:04
@Rubbish_DuTa是谁啊
by furina_yyds @ 2025-01-10 16:29:30
太久没上都掉了
by Rubbish_Du @ 2025-01-10 16:29:46
@furina_yyds 学弟
by Rubbish_Du @ 2025-01-10 16:30:55
@furina_yyds?