RE 0pts 求条
查看原帖
RE 0pts 求条
148875
NaNO2_Cabbage楼主2023/9/12 15:08

#include <bits/stdc++.h>
#define upf(i,n,k) for(int i=k;i<=n;i++)
#define lowf(i,n,k) for(int i=n;i>=k;i--)
#define Max(a,b,c) max(a,max(b,c))
#define Min(a,b,c) min(a,min(b,c))
#define ofile(N) freopen(N".in","r",stdin),freopen(N".out","w",stdout)
#define ri register int
#define ie inline
#define ll long long
using namespace std;

ie int read() {
	int s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')w = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}

ie void out(int a) {
	if (a >= 10)out(a / 10);
	putchar(a % 10 + '0');
}

int n, m;
vector<int> g[4000050];
vector<int> e[4000050];
int low[4000050], dfn[4000050], scc[4000050], vis[4000050], col, num;
stack<int> s;

inline void tarjan(int u, int fa) {
	int son = 0;
	low[u] = dfn[u] = ++num;
	vis[u] = 1;
	s.push(u);
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (!dfn[v]) {
			++son;
			tarjan(v, u), low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u]) {
				col++;
				e[col].push_back(s.top());
				s.pop();
				while (s.top() != v)e[col].push_back(s.top()), s.pop();
				s.pop();
				e[col].push_back(v);
				e[col].push_back(u);
			}
		} else if (v != fa)low[u] = min(low[u], dfn[v]);
	}
	if (fa == 0 && son == 0)e[++col].push_back(u);
}

int main() {
	//ofile("");
	n = read(), m = read();
	while (m--) {
		int u = read(), v = read();
		g[u].push_back(v), g[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		while(!s.empty())s.pop();
		if (!dfn[i])tarjan(i, 0);
	}
	printf("%d\n", col);
	for (int i = 1; i <= col; i++) {
		printf("%d ", e[i].size());
		for (auto j : e[i])printf("%d ", j);
		puts("");
	}
	return 0;
}

```cpp
2023/9/12 15:08
加载中...