求助，并查集实现

> 在牛客上有一道实现并查集的题，https://www.nowcoder.com/questionTerminal/e7ed657974934a30b2010046536a5372 > 我用结构体来实现一个并查集 可以通过用例，代码如下 ```go package main import ( "bufio" "os" ) var in, out = bufio.NewReader(os.Stdin), bufio.NewWriter(os.Stdout) func read() int { ret := 0 for c, _ := in.ReadByte(); c >= '0' && c <= '9'; c, _ = in.ReadByte() { ret = (ret * 10) + int(c-'0') } return ret } func main() { var m, n int m,n = read(),read() // 创建并查集 u := NewNowCoder(m) var opt, x, y int for i := 0; i < n; i++ { opt,x,y = read(),read(),read() if opt == 1 { if u.isSameSet(x, y) { out.WriteString("Yes\n") } else { out.WriteString("No\n") } } else { u.union(x, y) } } out.Flush() } type NowCoder struct { // 指向前面的节点(索引代表当前值，值代表父节点指针) father []int // 每个并查集的大小 size []int // 记录寻找代表节点时沿途遇到的节点（帮助扁平化） stack []int } func NewNowCoder(l int) *NowCoder { res := &NowCoder{ father: make([]int, l), size: make([]int, l), } for i := 0; i < l; i++ { res.father[i] = i res.size[i] = 1 } return res } // 查找某个值所在集合的代表节点 func (n *NowCoder) find(value int) int { for n.father[value] != value { // 将沿途节点添加到栈中 n.stack = append(n.stack, value) value = n.father[value] } // 扁平化 for i := 0; i < len(n.stack); i++ { n.father[n.stack[i]] = value } n.stack = make([]int, 0) return value } // 判断两个值是否在同一集合 func (n *NowCoder) isSameSet(v1, v2 int) bool { return n.find(v1) == n.find(v2) } // 合并两个元素所在的集合 func (n *NowCoder) union(v1, v2 int) { f1, f2 := n.find(v1), n.find(v2) // 小挂大 if n.size[f1] > n.size[f2] { n.size[f1] += n.size[f2] n.father[f2] = f1 } else { n.size[f2] += n.size[f1] n.father[f1] = f2 } } ``` > 然后我就觉得可以不用结构体，直接把father数组当成全局变量也行，我就把代码改成了这样 ```go package main import ( "os" "bufio" ) var in, out = bufio.NewReader(os.Stdin), bufio.NewWriter(os.Stdout) func read() int { ret := 0 for c, _ := in.ReadByte(); c >= '0' && c <= '9'; c, _ = in.ReadByte() { ret = (ret * 10) + int(c-'0') } return ret } var father []int var stack []int // 构建并查集 func buildUnionFind(n int) { father = make([]int, n) for i := 0; i < n; i++ { father[i] = i } } // 查找元素的代表节点 func find(n int) int { for father[n] != n { stack = append(stack,n) n = father[n] } // 扁平化 for i:=0;i<len(stack);i++{ father[stack[i]] = n } return n } // 判断两个元素是否在一个集合中 func isSameset(x, y int) bool { return find(x) == find(y) } // 合并集合 func union(x, y int) { f1, f2 := father[x], father[y] father[f1] = f2 } func main(){ n,m:= read(),read() buildUnionFind(n) var x,y,z int for i:=0;i<m;i++{ z,x,y = read(),read(),read() if z == 2 { union(x,y) }else { if isSameset(x,y){ out.WriteString("Yes\n") }else{ out.WriteString("No\n") } } } out.Flush() } ``` > 但这样会超出内存限制，有大佬知道这是为什么吗？