提交记录

题目link

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;

const int MAXN = 2e6 + 10;
const int MAXM = 2e6 + 10;
int head[MAXN],dfn[MAXN],low[MAXN];
bool bridge[MAXN],vis[MAXN];
int cnt=1,num=0,tot=0,n,m;
vector<int>ans[MAXN];
struct node{
	int nxt,v;
	bool fl;
}e[MAXM<<1];
void add_edge(int u,int v){
	e[++cnt].v=v;
	e[cnt].fl=0;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
void tarjan(int x,int in){
	dfn[x]=low[x]=++tot;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].v;
		if(!dfn[y]){
			tarjan(y,i);
			low[x]=min(low[x],low[y]);
			if(dfn[x]<low[y]) bridge[i]=bridge[i^1]=1;
		}
		else if(i!=(in^1)) low[x]=min(low[x],dfn[y]);
	} 
}
void dfs(int x){
	ans[num].push_back(x);
	vis[x]=1;
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].v;
		if(vis[v]||bridge[i]) continue;
		dfs(v);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	FL(i,1,m){
		int u,v;
		scanf("%d%d",&u,&v);
		add_edge(u,v);
		add_edge(v,u);
	}
	FL(i,1,n){
		if(!dfn[i]){
			tarjan(i,0);
		}
	}
	FL(i,1,n){
		if(!vis[i]){
			num++;
			dfs(i);
		}
	}
    printf("%d\n",num);
    FL(i,1,num){
		printf("%d ",ans[i].size());
		FL(j,0,ans[i].size()-1){
			printf("%d ",ans[i][j]);
		}
		printf("\n");
	}
	return 0;
}