求助,并查集实现

xianren68 · · 832 次点击 · 开始浏览    置顶
这是一个创建于 的主题,其中的信息可能已经有所发展或是发生改变。

> 在牛客上有一道实现并查集的题,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() } ``` > 但这样会超出内存限制,有大佬知道这是为什么吗?

有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

832 次点击  
加入收藏 微博
1 回复  |  直到 2023-10-09 10:24:00
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传