并查集

package main  
  
import "fmt"  
  
type UnionFind struct {  
   parent []int  
}  
  
// NewUnionFind 集合初始化
func NewUnionFind(n int) UnionFind {  
   fa := make([]int, n)  
   for i := range fa {  
      fa[i] = i  
   }  
   return UnionFind{fa}  
}  
  
// Find 寻找根节点(带压缩)
func (u *UnionFind) Find(x int) int {  
   if u.parent[x] != x {  
      u.parent[x] = u.Find(u.parent[x])  
   }  
   return u.parent[x]  
}  
  
// Merge 合并
func (u *UnionFind) Merge(x, y int) {  
   rx := u.Find(x)  
   ry := u.Find(y)  
   if rx != ry {  
      u.parent[rx] = u.parent[ry]  
   }  
}  
  
// Same 判断是否在同一集合(在合并操作之后父亲节点不一定是根节点,不能直接比较)
func (u *UnionFind) Same(x, y int) bool {  
   return u.Find(x) == u.Find(y)  
}  
  
func Main() {  
   u := NewUnionFind(10)  
   fmt.Println(u.Find(2))  
}