Mahdi Ghadamyari

class Graph {
	verticies = {};

	add(vertix, adjacencies) {
		if (!this.verticies[vertix]) this.verticies[vertix] = new Set();

		for (const adjacent of adjacencies) {
			if (vertix == adjacent) continue;
			if (!this.verticies[adjacent]) this.verticies[adjacent] = new Set();
			this.verticies[vertix].add(adjacent);
			this.verticies[adjacent].add(vertix);
		}
	}
}

class UnionFind {
	constructor(n) {
		this.root = new Array(n).fill(null).map((x, idx) => idx);
		this.rank = new Array(n).fill(1);
		this.vertexCount = n;
	}
	find(v) {
		if (v === this.root[v]) {
			return v;
		}
		this.root[v] = this.find(this.root[v]);
		return this.root[v];
	}
	union(v1, v2) {
		const r1 = this.find(v1),
			r2 = this.find(v2);

		if (r1 === r2) {
			return;
		}
		if (this.rank[r1] > this.rank[r2]) {
			this.root[r2] = r1;
		} else if (this.rank[r1] < this.rank[r2]) {
			this.root[r1] = r2;
		} else {
			this.root[r2] = r1;
			this.rank[r1] += 1;
		}
	}
	disjointSets() {
		const map = new Map();
		for (let i = 0; i < this.vertexCount; ++i) {
			const root = this.find(i);
			const vtx = map.has(root) ? map.get(root) : [];
			vtx.push(i);
			map.set(root, vtx);
		}
		return map;
	}
}

class UnionFind {
	constructor(nums) {
		this.root = new Map();
		this.rank = new Map();
		for (const num of nums) {
			this.root.set(num, num);
			this.rank.set(num, 1);
		}
		this.nums = nums;
	}
	find(v) {
		if (v === this.root.get(v)) {
			return v;
		}
		this.root.set(v, this.find(this.root.get(v)));
		return this.root.get(v);
	}
	union(v1, v2) {
		const r1 = this.find(v1),
			r2 = this.find(v2);

		if (r1 === r2) {
			return;
		}
		if (this.rank.get(r1) > this.rank.get(r2)) {
			this.root.set(r2, r1);
		} else if (this.rank.get(r1) < this.rank.get(r2)) {
			this.root.set(r1, r2);
		} else {
			this.root.set(r2, r1);
			this.rank.set(r1, this.rank.get(r1) + 1);
		}
	}
	disjointSets() {
		const map = new Map();
		for (let i = 0; i < this.nums.length; i++) {
			const root = this.find(this.nums[i]);
			const vtx = map.has(root) ? map.get(root) : [];
			vtx.push(this.nums[i]);
			map.set(root, vtx);
		}
		return map;
	}
}