Skip to content

Instantly share code, notes, and snippets.

@tungurlakachakcak
Created August 26, 2022 15:51
Show Gist options
  • Save tungurlakachakcak/5d332126d3a3c61bc759da0a9281c620 to your computer and use it in GitHub Desktop.
Save tungurlakachakcak/5d332126d3a3c61bc759da0a9281c620 to your computer and use it in GitHub Desktop.
#include <iostream>
#include <vector>
#include <future>
#include <unordered_map>
#include <unordered_set>
using namespace std;
/* A DS for finding the root node of a vertex in a tree.
!Does not keep track of the original tree structure so it cannot be reconstructed exactly. */
class DisjointSet {
public:
DisjointSet(int n) : _n(n), vertices(new int[n]) {
for (int i = 0; i < n; i++) {
vertices[i] = i;
}
}
virtual ~DisjointSet() {
delete[] vertices;
}
virtual int find(int vertex) const = 0;
virtual void union_(int vertex1, int vertex2) const = 0;
bool connected(int v1, int v2) const {
return find(v1) == find(v2);
}
virtual void print() const {
for (int i = 0; i < _n; i++) {
cout << vertices[i] << " ";
}
cout << endl;
}
protected:
int _n;
int* vertices;
};
class FastFindSlowUnionSet : public DisjointSet {
public:
FastFindSlowUnionSet(int n) : DisjointSet(n) {}
/* O(1) */
int find(int vertex) const {
return vertices[vertex];
}
/* O(n) */
void union_(int vertex1, int vertex2) const {
int vertex1Root = vertices[vertex1];
int vertex2Root = vertices[vertex2];
if (vertex1Root == vertex2Root) {
return;
}
vertices[vertex2] = vertex1Root;
for (int i = 0; i < _n; i++) {
if (vertices[i] == vertex2) {
vertices[i] = vertex1Root;
}
}
}
};
class FastUnionSlowFindSet : public DisjointSet {
public:
FastUnionSlowFindSet(int n) : DisjointSet(n) {
rank = new int[n];
for (int i = 0; i < n; i++) {
rank[i] = 1;
}
}
~FastUnionSlowFindSet() {
delete[] rank;
}
int find(int vertex) const {
if (vertices[vertex] == vertex) {
return vertex;
}
int root = find(vertices[vertex]);
vertices[vertex] = root;
return root;
}
void union_(int v1, int v2) const {
int v1Root = find(v1);
int v2Root = find(v2);
if (v1Root == v2Root) {
return;
}
if (rank[v1Root] > rank[v2Root]) {
vertices[v2Root] = v1Root;
}
else if (rank[v1Root] < rank[v2Root]) {
vertices[v1Root] = v2Root;
}
else {
vertices[v2Root] = v1Root;
rank[v2Root] += 1;
}
}
void print() const override {
cout << "Vertices: " << endl;
DisjointSet::print();
cout << "Rank: " << endl;
for (int i = 0; i < _n; i++) {
cout << rank[i] << " ";
}
cout << endl;
}
private:
int* rank;
};
int main() {
DisjointSet* disi = new FastUnionSlowFindSet(10);
disi->union_(1, 2);
disi->print();
disi->union_(2, 5);
disi->print();
disi->union_(5, 6);
disi->print();
disi->union_(6, 7);
disi->print();
disi->union_(3, 8);
disi->union_(8, 9);
disi->print();
cout << disi->connected(7, 1) << endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment