求调直接用vector装过不了
查看原帖
求调直接用vector装过不了
1193780
wuhusjqif楼主2024/7/1 17:43
#include <bits/stdc++.h>
using namespace std;
const int N = (int)2e6 + 5;
int tot,head[N],pre[2*N],to[2*N];
int idx,dfn[N],low[N],n,m;]
stack <int> stk;
vector <vector <int>> res;
void add(int u,int v) {
	to[++tot] = v;
	pre[tot] = head[u];
	head[u] = tot;
}
void tarjan(int x,int edg) {
	dfn[x] = low[x] = ++idx;
	stk.push(x);
	for(int j = head[x];j;j = pre[j]) {
		int y = to[j];
		if(!dfn[y]) {
			tarjan(y,j);
			low[x] = min(low[x],low[y]);
		}
		else if(j != (edg ^ 1)) low[x] = min(low[x],dfn[y]);
	}
	if(dfn[x] == low[x]) {
		vector <int> ans;
		while(1) {
			int g = stk.top();stk.pop();
			ans.push_back(g);
			if(g == x) break;
		}
		res.push_back(ans);
	}
}
signed main() {
	cin >> n >> m;
	for(int u,v;m; --m) {
		cin >> u >> v;
		if(u == v) continue;
		add(u,v);
		add(v,u);
	}
	for(int i = 1;i <= n; ++i) if(!dfn[i]) tarjan(i,-1);
	cout << res.size() << endl;
	for(auto p : res) {
		cout << p.size() << ' ';
		for(auto f : p) cout << f << ' ';
		cout << endl;
	}
	return 0;
}

~~

2024/7/1 17:43
加载中...