WA on #4,5,8,11,13,22求助
查看原帖
WA on #4,5,8,11,13,22求助
1287433
__ycy1124__楼主2024/9/29 10:45
#include<bits/stdc++.h>
#define int long long
using namespace std;
vector <int> a[600005];
int n,m;
int fa[600005],dfn[600005],low[600005];
int idx=0;
bool bj[600005];
struct Node{
	queue<int>p;
	int cnt;
}ans[600005];
int tot=0;
void dfs(int p,int f){
	dfn[p]=low[p]=++idx;
	fa[p]=f;
	for(auto it:a[p]){
		if(!dfn[it]){
			fa[it]=p;
			dfs(it,p);
			low[p]=min(low[p],low[it]);
			if(low[it]>dfn[p]){
				bj[it]=1;
			}
		}
		else if(it!=fa[p]){
			low[p]=min(dfn[it],low[p]);
		}
	}
}
void Tanjan(){
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			dfs(i,0);
		}
	}
}
bool vis[600005];
void Dfs(int p){
	vis[p]=1;
	ans[tot].cnt++;
	ans[tot].p.push(p);
	for(auto it:a[p]){
		if((bj[p]&&fa[p]==it)||(bj[it]&&fa[it]==p)||vis[it]){
			continue;
		}
		Dfs(it);
	}
}
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		a[u].push_back(v);
		a[v].push_back(u);
	}
	Tanjan();
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			++tot;
			Dfs(i);
		}
	}
//	printf("\n");
//	for(int i=1;i<=n;i++){
//		if(bj[i]){
//			printf("%d %d\n",i,fa[i]);
//		}
//	}
	printf("%d\n",tot);
	for(int i=1;i<=tot;i++){
		printf("%d",ans[i].cnt);
		while(!ans[i].p.empty()){
			printf(" %d",ans[i].p.front());
			ans[i].p.pop();
		}
		printf("\n");
	}
	return 0;
}
2024/9/29 10:45
加载中...