> 在牛客上有一道实现并查集的题，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()
}
```
> 但这样会超出内存限制，有大佬知道这是为什么吗？
有疑问加站长微信联系（非本文作者）
