0pts,样例3过不了,玄关
查看原帖
0pts,样例3过不了,玄关
769006
crzcqh楼主2024/12/28 10:46
#include<bits/stdc++.h>
using namespace std;
const int M=2e6+5;
const int N=2e5+5; 
int n,m,u,v,cnt=1,tot,ans;
int head[N],dfn[N],low[N],flag[M],c[M]; 
pair<int,int> edge[M];
map<pair<int,int>,int> f;
vector<int> eans[N];
void add(int u,int v){
	cnt++;
	edge[cnt].first=v;
	edge[cnt].second=head[u];
	head[u]=cnt;
	
}
void tarjan(int u,int l){
	dfn[u]=low[u]=++tot;
	for(int i=head[u];i;i=edge[i].second){
		v=edge[i].first;
		if(!dfn[v]){
			tarjan(v,i);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u])
				flag[i]=flag[i^1]=1;			
		}else if(i!=(l^1))               
			low[u]=min(low[u],dfn[v]);
	}
}
void dfs(int u){
	c[u]=ans;
	eans[ans].push_back(u);
	for(int i=head[u];i;i=edge[i].second){
		v=edge[i].first;
		if(c[v]||flag[i])
			continue;
		dfs(v);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		if(f[make_pair(u,v)]==1) continue;
		add(u,v),add(v,u);
		f[make_pair(u,v)]=f[make_pair(v,u)]=1;
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]) tarjan(i,0);
	for(int i=1;i<=n;i++)
		if(!c[i]){
			ans++,dfs(i);
		}
	cout<<ans<<endl;
	for(int i=1;i<=ans;i++){
		cout<<eans[i].size()<<' ';
		for(int v : eans[i]) cout<<v<<' ';
		cout<<endl;
	}
	return 0;
} 
2024/12/28 10:46
加载中...