求调。
查看原帖
求调。
555381
zlttcl楼主2024/7/25 10:29

样例 22 直接输出了一万个 1010。交上去 30pts。。好像是存父亲的时候爆了,有很多重边。

//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e6 + 10;
ll n, m, cnt = 1, dep, _dep;
int dfn[N], cut[N], _dfn[N], low[N], f[N];
bool cut1[N], on_tree[N];
ull w[N];
gp_hash_table<ull, bool> st;
gp_hash_table<ull, int> mp;
vector<int> vec[N], g[N];
vector<vector<int>> ans;
inline ll read() {
	ll x = 0, m = 1;
	char ch = getchar();
	while(!isdigit(ch)) {
		if(ch == '-') m = -1;
		ch = getchar();
	}
	while(isdigit(ch)) {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * m;
}
inline void write(ll x) {
	if(x < 0) {
		putchar('-');
		write(-x);
		return;
	}
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}
mt19937 rnd(time(NULL));
inline ull get_rnd() {
	return rnd() | 1ull * rnd() << 32;
}
inline void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++ dep;
	for(int i = 0; i < vec[u].size(); ++ i) {
		int v = vec[u][i];
		if(g[u][i] == (fa ^ 1)) continue;
		if(!dfn[v]) {
			tarjan(v, g[u][i]);
			low[u] = min(low[u], low[v]);
			if(low[v] >= dfn[v]) cut[g[u][i]] = cut[g[u][i] ^ 1] = 1;
		} else low[u] = min(low[u], dfn[v]);
	}
}
inline void dfs3(int u, int vv, vector<int> &now) {
	now.push_back(u);
	for(int i = 0; i < vec[u].size(); ++ i) {
		int v = vec[u][i];
		if(cut[g[u][i]] || cut1[g[u][i]] || !on_tree[g[u][i]] || v == vv) continue;
		dfs3(v, vv, now);
	}
}
int aa;
inline void dfs2(int u, int fa) {
//	if(++ aa < 20) for(int i = 0; i < vec[10].size(); ++ i) cout << vec[10][i] << endl;
	for(int i = 0; i < vec[u].size(); ++ i) {
		int v = vec[u][i];
		if(cut[g[u][i]] || cut1[g[u][i]] || !on_tree[g[u][i]]) continue;
		dfs2(v, g[u][i]);
	}
	if(mp.find(w[u]) != mp.end()) {
		int v = mp[w[u]];
		vector<int> tmp;
		dfs3(u, v, tmp);
		ans.push_back(tmp);
		vec[f[u]].push_back(v), g[f[u]].push_back(++ cnt);
		on_tree[fa] = 0, on_tree[cnt] = 1, f[v] = f[u];
		mp[w[u]] = v;
	} else mp[w[u]] = u;
}
inline void dfs1(int u, int fa) {
	_dfn[u] = ++ _dep;
	for(int i = 0; i < vec[u].size(); ++ i) {
		int v = vec[u][i];
		if(g[u][i] == (fa ^ 1) || cut[g[u][i]]) continue;
		if(_dfn[v]) {
			if(_dfn[v] > _dfn[u]) continue;
			ull val = get_rnd();
			w[u] ^= val, w[v] ^= val;
			st[val] = 1;
		} else {
			on_tree[g[u][i]] = 1, f[v] = u;
			dfs1(v, g[u][i]);
			w[u] ^= w[v];
		}
	}
	if(st.find(w[u]) != st.end()) cut1[fa] = cut1[fa ^ 1] = 1;
	if(cut1[fa] || !fa) {
		mp.clear();
		dfs2(u, 0);
		vector<int> tmp;
		dfs3(u, 0, tmp);
		ans.push_back(tmp);
	}
}
signed main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	n = read(), m = read();
	for(int i = 1; i <= m; ++ i) {
		int u = read(), v = read();
		vec[u].push_back(v), vec[v].push_back(u);
		g[u].push_back(++ cnt), g[v].push_back(++ cnt);
	}
	for(int i = 1; i <= n; ++ i) if(!dfn[i]) tarjan(i, 0);
	for(int i = 1; i <= n; ++ i) if(!_dfn[i]) dfs1(i, 0);
	for(vector<int> &v : ans) sort(v.begin(), v.end());
	sort(ans.begin(), ans.end());
	write(ans.size()), putchar('\n');
	for(vector<int> v : ans) {
		for(int x : v) write(x), putchar(' ');
		putchar('\n');
	}
	return 0;
}


2024/7/25 10:29
加载中...