Subtask #4 不过求调
查看原帖
Subtask #4 不过求调
809765
Limitless_lmw楼主2024/11/29 18:13
#include <bits/stdc++.h>
using namespace std;

const int maxn=2e5+5;
int head[maxn], nxt[maxn], to[maxn], tot = 1;

inline void add_V(int b,int e){
	nxt[++tot] = head[b];
	to[head[b] = tot] = e;
	return ;
}

int dfn[maxn], low[maxn], st[maxn], top;
bool ins[maxn];
int cnt, idx, bel[maxn];
vector<int> ans[maxn];
int anscnt;
int n,m;

void dfs(int u, int lst){
	low[u] = dfn[u] = ++cnt;
	st[++top] = u;
	for(int i = head[u]; i; i = nxt[i]){
		if(i == (lst ^ 1)) continue;
		if(!dfn[to[i]]){
			dfs(to[i], i);
			low[u] = min(low[u],low[to[i]]);
		}else low[u] = min(low[u],dfn[to[i]]);
	}
	if(low[u] == dfn[u]){
		int v; ++idx;
		do{
			v = st[top--];
			bel[v] = idx;
			ans[bel[v]].push_back(v);
		}while(u ^ v);
	}
	return ;
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i = 1,u,v; i<=m; i++){
		scanf("%d %d",&u,&v);
		add_V(u,v),add_V(v,u);
	}
	for(int i = 1; i<=n; i++){
		if(!dfn[i]) dfs(i,-1);
	}
	printf("%d\n",idx);
	for(int i = 1; i<=idx; i++){
		printf("%d ",ans[i].size());
		for(auto t:ans[i]) printf("%d ",t);
		puts("");
	}
	return 0;
}
2024/11/29 18:13
加载中...