玄关求调
查看原帖
玄关求调
1046223
a_blue_fool楼主2024/11/25 14:08
#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>

#define N 5 * 100000 + 5
#define pb push_back

using namespace std;

int n, m, cnt, tot, root;
int dfn[N], low[N];
vector <int> g[N], ans[N];
stack <int> s;

inline void add(int u, int v) {
	g[u].pb(v);
	g[v].pb(u);
}

void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++cnt;
	int child = 0;
	s.push(u);
	
	for (auto v : g[u]) {
		if (!dfn[v]) {
			child++;
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
			
			if (low[v] >= dfn[u]) {
				tot++;
				
				while(s.top() != u) {
					ans[tot].pb(s.top());
					s.pop();
				}
				
				ans[tot].pb(u);
			}
		}
		else if(v != fa)
			low[u] = min(low[u], dfn[v]);
	}
	
	if (u == root && child == 0) {
		tot++;
		ans[tot].pb(u);
	}
	
	return;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1, u, v; i <= m; i++) {
		scanf("%d%d", &u, &v);
		add(u, v);
	}
	
	for (root = 1; root <= n; root++)
		if (!dfn[root]) {
			while(!s.empty())
				s.pop();
			
			tarjan(root, 0);
		}
		
	
	printf("%d\n", tot);
	for (int i = 1; i <= tot; i++) {
		printf("%d ", ans[i].size());
		
		for (auto j : ans[i])
			printf("%d ", j);
		printf("\n");
	}
	
	return 0;
}
2024/11/25 14:08
加载中...