求助
查看原帖
求助
717599
dengjunhaodejia09楼主2023/4/10 14:41
#include<bits/stdc++.h>
using namespace std;

int n,m,dfn[1000010],low[1000010],x,y,head[1000010],cnt,tot;
struct edge{
	int to,next;
}e[2000010];
void add(int u,int v){
	e[++cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
inline int read(){
	int step=1,s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
	    if(ch=='-')step=-1;
	    ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
	    s=(s<<1)+(s<<3)+ch-'0';
	    ch=getchar();
	}
	return step*s;
}
queue <int> dd; 
void tarjan(int cur,int root){
	dfn[cur]=low[cur]=++tot;
	for(int i=head[cur];i;i=e[i].next){
		int y=e[i].to;
		if(y==0){
			continue;
		}
		if(dfn[y]==0){
			tarjan(y,i);
			low[cur]=min(low[y],low[cur]);
			if(dfn[cur]<low[y])dd.push(i);;
		}else if(i!=(root^1))low[cur]=min(low[cur],dfn[y]);
	}
}
bool p[1000001];
queue <int> q;
void dfs(int k){
	p[k]=true;
	q.push(k);
	for(int i=head[k];i;i=e[i].next){
		if(e[i].to==0){
			continue;
		}
		if(p[e[i].to]==false){
			dfs(e[i].to);
		}
	}
}
int main(){
	n=read(),m=read();
	cnt=1;
	for(int i=1;i<=m;i++){
		x=read(),y=read();
		add(x,y);
		add(y,x);
	}
	for(inti=1;i<=n;i++)if(!dfn[i])tarjan(i,0);
	while(!dd.empty()){
		e[dd.front()].to=0;
		dd.pop();
	}
	int g=0;
	for(int i=1;i<=n;i++){
		if(p[i]){
			continue;
		}
		while(!q.empty()){
			q.pop();
		}
		if(p[i]==false){
			dfs(i);
		}
		g++;
	}
	cout<<g<<endl;
	memset(p,false,sizeof(p));
	for(int i=1;i<=n;i++){
		if(p[i]){
			continue;
		}
		while(!q.empty()){
			q.pop();
		}
		if(p[i]==false){
			dfs(i);
		}
		cout<<q.size()<<" ";
		int ooo=q.size();
		for(int i=1;i<=ooo;i++){
			cout<<q.front()<<" ";
			q.pop();
		}
		cout<<endl;
	}
	
	return 0;
}
2023/4/10 14:41
加载中...