DSU
(DS/DSU.hpp)

• View this file on GitHub
• Last update: 2024-05-22 23:19:36+07:00
• Include: #include "DS/DSU.hpp"

Description:

Disjoint Set Union with path compression and union by size. Add edges and test connectivity. Use for Kruskal’s or Boruvka’s minimum spanning tree.

Usage:

• DSU d;
• d.init(size)

Time:

• $O(\alpha(N))$

Verified with

• test/aizu/disjointset.test.cpp
• test/yosupo/Ds/unionfind_yosupo.test.cpp
• test/yosupo/Graph/MST_yosupo.test.cpp

Code

#pragma once
struct DSU {
	vector<int> e; void init(int N) { e = vector<int>(N,-1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } 
	bool same(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) { // union by size
		x = get(x), y = get(y); if (x == y) return 0;
		if (e[x] > e[y]) swap(x,y);
		e[x] += e[y]; e[y] = x; return 1;
	}
};

#line 2 "DS/DSU.hpp"
struct DSU {
	vector<int> e; void init(int N) { e = vector<int>(N,-1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } 
	bool same(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) { // union by size
		x = get(x), y = get(y); if (x == y) return 0;
		if (e[x] > e[y]) swap(x,y);
		e[x] += e[y]; e[y] = x; return 1;
	}
};

Back to top page