package main

// 0.先整一个并查集struct
type DisjoinSets struct {
	parent , size [] int //父节点/深度 数组
	count int // 连通分量,一开始最大，后续逐渐减小
}

// 1.init函数
func (djset *DisjoinSets) init (n int){
	djset.parent = make([]int,n,n)
	for i := range djset.parent {
		djset.parent[i] = i
	}
	djset.size = make([]int , n ,n )
	for i := range djset.size {
		djset.size[i] = 1
	}
	djset.count = n
}

// 2.find函数，寻找父节点
func (djSet *DisjoinSets) find (idx int) int {
	if djSet.parent[idx] != idx  {
		return djSet.find(djSet.parent[idx])
	}
	return djSet.parent[idx]
}

// 3.union函数，合并集合
func (djSet *DisjoinSets) union (x, y int) bool {
	// 一共三种情况 TODO 合并指的都是父节点的合并，子节点没有合并的必要性。
	// 1. x,y在同一个集合中
	// TODO 重要！这里的size是指父节点的size，这样就不用每次去更新每个节点的size了!
	px , py := djSet.find(x) , djSet.find(y)
	if  px == py    {
		return false
	}
	// 2. x,y不在同一个集合中,合并集合
	xSize , ySize := djSet.size[px] , djSet.size[py]
	if ySize > xSize {
		px , py = py ,px
	}
	djSet.parent[py] = px
	djSet.size[px] += djSet.size[py]
	djSet.count --
	return true
}

// 连通网络的操作次数 ，标准的并查集模板即可解
func makeConnected(n int, connections [][]int) int {
	if len(connections) < n -1 {
		return -1
	}
	var djSet DisjoinSets
	djSet.init(n)
	for  _ , v  := range connections {
		djSet.union(v[0],v[1])
	}
	// 返回线的数量 - 连通分量所需的线数量
	return djSet.count - 1
}