题解 | 并查集的实现

package main

import (
	"fmt"
	"os"
	"bufio"
)

//具体题解参见左神bili代码讲解，这里仅提供go模版，输出部分可替换，但是目前优化过输入后已经不超时了。https://www.bilibili.com/video/BV1894y1W7Sb/?spm_id_from=333.337.search-card.all.click
func main() {
  //in用于输入优化，否则超时
	in:= bufio.NewReaderSize(os.Stdin,1<<20)
  //out引入未使用，可以用于打印输出
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	var n, m int
	fmt.Fscan(in,&n, &m)
	father := make([]int, n+1)
	size:=make([]int,n+1)
	stack:=make([]int,n+1)
	for i := 1; i <= n; i++ {
		father[i] = i
		size[i]=1
	}
	var find func(i int) int
	find = func(i int) int {
		cnt:=0
		for father[i] != i {
			stack[cnt]=i
			cnt++
			i = father[i]
		}
		for cnt>0{
			cnt--
			father[stack[cnt]]=i
		}
		return i
	}

	var unionSet func(i, j int)
	unionSet = func(i, j int) {
		fi := find(i)
		fj := find(j)
		if fi != fj {
			if size[fi]>=size[fj]{
				father[fj]=fi
				size[fi]+=size[fj]
			}else{
				size[fj]+=size[fi]
				father[fi]=fj
			}
		}
	}

	var isSameSet func(i, j int) string
	isSameSet = func(i, j int) string {
		fi := find(i)
		fj := find(j)
		if fi != fj {
			return "No"
		}
		return "Yes"
	}

	for i := 0; i < m; i++ {
		var j, k, l int
		fmt.Fscan(in,&j, &k, &l)
		if j == 1 {
			fmt.Println(isSameSet(k, l))
		} else {
			unionSet(k, l)
		}
		// fmt.Println(father)
	}

}