Union Find Set

1. Introduction

2. Methods

2.1 find()

The average time complexity of compressed find is O(1).

public int find(int x) {
	
	if (parent[x] == x) return x;
	
	parent[x] = find(x);
	
	return parent[x];
}

2.2 union()

public void union (int x, int y) {
	
	int px = find(x), py = find(y);

	if (px != py) parent[px] = py;
}