为什么这样写会错
查看原帖
为什么这样写会错
701387
xiaoliebao1115楼主2024/11/29 21:00
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int nn=5e5+5,mm=4e6+5;
int n,m,cnt,nxt[mm<<1],head[nn],timer,dfn[nn],low[nn],stac[nn],tp,bcc;
bool flg[nn];
vector<int> bc[nn];
struct node{
	int u,v;
}e[mm<<1];
void add(int u,int v){
	cnt++;
	e[cnt].u=u,e[cnt].v=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
void tarjan(int x,int father){
	dfn[x]=low[x]=++timer;
	stac[++tp]=x;
	int sl=0;
	for(int i=head[x];i;i=nxt[i]){
		int v=e[i].v;
		if(v==father) continue;
		if(!dfn[v]){
			sl++;
			tarjan(v,x);
			if(low[v]>=dfn[x]){
				bcc++;
				while(1){
					bc[bcc].pb(stac[tp]);
					if(stac[tp]==x) break;
					tp--;
				}
				flg[x]=1;
			}
			low[x]=min(low[x],low[v]);
		}
		else low[x]=min(low[x],dfn[v]);
	}
	if(sl==0&&x==father) bc[++bcc].pb(x);
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		add(v,u),add(u,v);
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) tp=0,tarjan(i,i);
	cout<<bcc<<endl;
	for(int i=1;i<=bcc;i++){
		cout<<bc[i].size()<<" ";
		for(int v:bc[i]) cout<<v<<" ";
		cout<<endl;
	}
	return 0;
}
2024/11/29 21:00
加载中...