腾讯笔试题：朋友圈[并查集、golang]

题目：解析：代码（Golang）


package main

import "fmt"

// 并查集

type Set struct {
	roots  map[int]int
	height map[int]int
}

func (this Set) append(x, y int) {
	xRoot := this.findRoot(x)
	yRoot := this.findRoot(y)

	if xRoot == 0 && yRoot == 0 {
		this.roots[x] = y
		this.roots[y] = y // 根指向自己
		this.height[y] = 1
	} else if xRoot == 0 && yRoot != 0 {// 注意判断条件写全
		this.roots[x] = yRoot
	} else if yRoot == 0 && xRoot != 0{
		this.roots[y] = xRoot
	} else {
		if this.height[xRoot] >= this.height[yRoot] {
			this.roots[yRoot] = xRoot                                          // 注意是yRoot的根

			// for k, v := range this.roots{
			// 	if v == yRoot{
			// 		this.roots[k] = xRoot
			// 	}
			// }

			this.height[xRoot] = max(this.height[xRoot], this.height[yRoot]+1) // 注意是xRoot的高度根据xRoot和yRoot的高度发生改变
		} else {
			this.roots[xRoot] = yRoot // 注意一个根指向另一个根

			// for k, v := range this.roots{
			// 	if v == xRoot{
			// 		this.roots[k] = yRoot
			// 	}
			// }
		}
	}
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 找父节点
func (this Set) findRoot(x int) int {
	for x != this.roots[x] {
		x = this.roots[x]
	}
	return x
}

// 最多结点的集合
func (this Set) maxCount() int {
	count := make(map[int]int)
	for k := range this.roots {
		count[this.findRoot(k)]++ // 注意这里的findRoot
	}

	// for _, v := range this.roots{
	// 	count[v]++
	// }

	res := 0
	for _, v := range count {
		res = max(res, v)
	}
	return res
}

func main() {

	var T int
	fmt.Scan(&T)
	for ; T != 0; T-- {
		set := Set{map[int]int{}, map[int]int{}}
		var n int
		fmt.Scan(&n)
		for ; n != 0; n-- {
			var x, y int
			fmt.Scan(&x, &y)
			set.append(x, y)
		}
		fmt.Println(set.maxCount())
	}
}

样例