Union-Find

 1type unionFind []int
 2
 3func newUnionFind(n int) *unionFind {
 4	uf := make(unionFind, n)
 5	for i := 0; i < n; i++ {
 6		uf[i] = -1
 7	}
 8	return &uf
 9}
10
11func (uf unionFind) Find(x int) int {
12	if uf[x] < 0 {
13		return x
14	}
15	uf[x] = uf.Find(uf[x])
16	return uf[x]
17}
18
19func (uf unionFind) Unite(x, y int) bool {
20	x, y = uf.Find(x), uf.Find(y)
21	if x != y {
22		if uf[x] > uf[y] {
23			x, y = y, x
24		}
25		uf[x] += uf[y]
26		uf[y] = x
27		return true
28	}
29	return false
30}
31
32func (uf unionFind) Same(x, y int) bool {
33	return uf.Find(x) == uf.Find(y)
34}
35
36func (uf unionFind) Size(x int) int {
37	return -uf[uf.Find(x)]
38}
39