スナップショットを撮って，その時点までロールバックできるDSU (daylight/structure/rollback_dsu.hpp)

• View this file on GitHub
• Last update: 2024-12-26 20:32:55+09:00
• Include: #include "daylight/structure/rollback_dsu.hpp"

Depends on

• 基本テンプレート (daylight/base.hpp)

Verified with

• test/yosupo/structure/persistent_unionfind.test.cpp
• test/yosupo/structure/unionfind.2.test.cpp

Code

#include "daylight/base.hpp"
/// @brief スナップショットを撮って，その時点までロールバックできるDSU
class rollback_dsu {
public:
	int N;
	vi p;
	stack<PI> history;
	rollback_dsu() {
	}
	rollback_dsu(int size): N(size) {
		p.resize(N, -1);
	}

	//同じ木に属しているか判定
	bool same(int x, int y) {
		return leader(x) == leader(y);
	}
	//xとyが属している木をつなぐ
	void merge(int x, int y) {
		link(leader(x), leader(y));
	}
	//木と木を繋ぐ処理をする。
	void link(int x, int y) {
		history.push({ x, p[x] });
		history.push({ y, p[y] });
		if(x == y) return;
		if(p[x] > p[y]) swap(x, y);
		if(p[x] == p[y]) {
			p[x]--;
		}
		p[y] = x;
	}
	//xが属している木の根を探る
	int leader(int x) {
		if(p[x] < 0)
			return x;
		else
			return leader(p[x]);
	}

	void undo() {
		p[history.top().first] = history.top().second;
		history.pop();
		p[history.top().first] = history.top().second;
		history.pop();
	}

	void snapshot() {
		while(!history.empty()) history.pop();
	}

	void rollback() {
		while(!history.empty()) {
			auto [i, v] = history.top();
			history.pop();
			p[i] = v;
		}
	}
};

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 482, in update
    self.update(
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 477, in update
    raise BundleErrorAt(
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: daylight/base.hpp: line 103: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page