开 O2 就 RE?
查看原帖
开 O2 就 RE?
556362
Unnamed114514楼主2023/4/1 11:14
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+5;
int n,m,tot,u[maxn],v[maxn],dfn[maxn],low[maxn],fa[maxn];
inline int Make(int n){
	for(int i=1;i<=n;++i)
		fa[i]=i;
}
int Find(int x){
	return fa[x]=(x==fa[x]?x:Find(fa[x]));
}
bool flg[maxn]; 
struct edge{
	int to,id;
};
vector<edge> G[maxn];
vector<int> g[maxn];
void Tarjan(int u,int fa){
	low[u]=dfn[u]=++tot;
	for(auto N:G[u]){
		int v=N.to,id=N.id;
		if(v==fa)
			continue;
		if(!dfn[v]){
			Tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<low[v])
				flg[id]=1;
		} else if(v!=fa)
			low[u]=min(low[u],dfn[v]);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u[i],&v[i]);
		G[u[i]].push_back(edge({v[i],i}));
		G[v[i]].push_back(edge({u[i],i}));
	}
	for(int i=1;i<=n;++i)
		if(!dfn[i])
			Tarjan(i,0);
	Make(n);
	for(int i=1;i<=m;++i)
		if(!flg[i])
			fa[Find(u[i])]=Find(v[i]);
	int cnt=0;
	for(int i=1;i<=n;++i){
		cnt+=(fa[i]==i);
		g[Find(i)].push_back(i);
	}
	printf("%d\n",cnt);
	for(int i=1;i<=n;++i)
		if(Find(i)==i){
			printf("%d",int(g[i].size()));
			for(auto v:g[i])
				printf(" %d",v);
			puts("");
		}
	return 0;
}
2023/4/1 11:14
加载中...