一个有意思的说明

并查集（Union-Find）为解决图的一类问题而生：

对于n个起初完全散落的节点，不断将它们两两相连，

在中间过程中，需要能迅速判断出两个节点是否已经相连，如果已经相连就不再连，没有则连接

可以类比为江湖建立各种门派的过程(参考 https://blog.csdn.net/niushuai666/article/details/6662911)：

有个程序员写了个武侠游戏，设定了一个特别的江湖世界：
江湖中共有n位大侠，按照程序员的习惯编号为0、1、2、……、n-1
一开始，所有人互相陌生
逐渐，人们开始互相认识， 2和5成为朋友，5和8成为朋友，……
有朋友关系的大侠开始组建帮派，如上面的2、5、8就成为一个帮派，虽然2和8还不认识，但因为中间人5的关系，他们三个成了一个帮派

渐渐地，帮派越来越多，每个帮派的人数也越来越多
程序员设定了一些规则：
每个人或者独行独往，或者最多加入一个门派，加入后不能退出，且仅仅认识帮派里自己的介绍人一个
那么要怎么迅速获知江湖里的两个人是不是属于同一个门派呢？

程序员可以为每个帮派指定一个帮主，这样可以用帮主来标识该帮，比如2、5、8组成的帮派选5为帮主，那么他们的帮派可称为“帮派5”

起初，所有人独来独往，可以看成共n个帮派，每个帮派的帮主就是帮派里唯一的那一位
有一天，2主动找5组建帮派，对于新帮派，2是自己的介绍人，2就作为帮主；5只知道自己加入了一个帮派，介绍人是2，但不知道帮主是谁，帮里还有谁
又有一天，5和8成了好友，5介绍8进了自己的帮派，8只认识帮派里的5

类似地，1和4组建帮派，1成为帮主，后来1又认识并介绍7加入帮派，7只知道自己有组织了，介绍人是1，但不知道组织里还有哪些大侠
之后9认识了4，被4介绍进了帮派1

只有程序员有上帝视角，知道每个帮派的帮主，每个人的介绍人
每个帮派的帮主知道自己是帮主，别人都只知道自己的介绍人

有一天，大侠9遇到了大侠7，他们想知道对方是不是和自己同一个帮派的，是就把酒言欢，否就大打出手
9先打电话给自己的介绍人4，4打电话给自己的介绍人1，1说他们的帮派名叫做“帮派1”，4又回拨9告诉帮派的名字
7先打电话给自己的介绍人1，1说他们的帮派名叫做“帮派1”
9和7一对，发现大家都是帮派1的人，好，喝酒吃肉去

大侠们都很健忘，每次都只记得自己的介绍人，忘了帮派名

又有一天，9和5相遇了，他们分别打电话给自己唯一认识的人，最终分别知道了自己所在的帮派，原来9属于帮派1，5属于帮派2
9在帮派1，5在帮派2，两人一对，大打出手
程序员于心不忍，打打杀杀不好玩，不如两个帮派合成一派吧，帮派1有1、4、7、9四个人，帮派2有2、5、8三个人，让帮派二并入帮派1吧
只需要让帮派2的帮主大侠2记录自己的介绍人为帮派1的帮主大侠1即可，这样帮派2的所有人并入了帮派1

程序员虽然是这个世界的上帝，不过也有难题，比如怎么迅速判断两个人是否属于同一个组织呢？一层层找帮主，时间复杂度有点高呢
好在这是个聪明的程序员，用数组模拟了这个世界，且想了些办法把帮派合并和查找某个人的帮派这两个操作好好优化了下

实现

type UnionFind []int

// 创建江湖世界
func NewUnionFind(n int) UnionFind {
	unionFind := make([]int, n)
	for i := range unionFind {
		unionFind[i] = i // 起初，每个人是自己的介绍人，也是自己的帮主
	}
	return unionFind
}

// x和y所在的两个帮派合并
func (uf UnionFind) Union(x, y int) {
    rootX, rootY := uf.Find(x), uf.Find(y) // 先找到各自的帮主
    // 两个帮派合并，rootX罢免自己的帮主之位，加入帮派rootY，介绍人成为rootY
    // （随便，反过来也可以。更好的做法是按秩合并，选人多的帮派帮主做合并后帮派的帮主，进一步减少整个Union、Find操作的复杂度）
    uf[rootX] = rootY   
}

// 寻找x的帮主
func (uf UnionFind) Find(x int) int {
	for uf[x] != x { // x的介绍人不是x自己，说明x不是帮主
		x = uf[x] // 一直向上找介绍人
	}
	return x // 自己的介绍人就是自己，这是帮主
}


// 一个简单有效的优化：
// 寻找x的帮主
func (uf UnionFind) Find(x int) int {
	for uf[x] != x { // x的介绍人不是x自己，说明x不是帮主
        // 路径压缩：找x介绍人的介绍人y，同时修改x的介绍人为y，这样组织才足够扁平化，后边再找帮主打电话的次数要少一些
		x, uf[x] = uf[x], uf[uf[x]]
	}
	return x // 自己的介绍人就是自己，这是帮主
}

最终实现参考