day1 AcWing 836. 合并集合

初始化：

n个下表对应n个集合，根节点的特征是父节点就是其本身。

for(int i = 1; i <= n; i++)

p[i] = i;

M操作：如果两个元素在同一个集合中，什么也不做，否则将两个集合合并；

Q操作：两个集合在同一个集合回复“Yes”，否则回复“No”；

核心思想：（1）两个集合合并，只需要将一个集合的根节点插入另一个集合，作为另一个集合的父节点即可；

（2）查询根节点判断祖先：使用路径压缩，对于一个集合中的元素x，在寻找根节点时，沿着根节点路径的所有节点都直接指向根节点。

find（int x）{ //返回 x 的根节点

if(p[x] != x) //父节点不是根节点

p[x] = find(p[x]); //递归向上寻找，根节点直接指向祖先节点

return p[x];

}

M: if(find(a) != find(b)){ // a, b分别在不同的集合中

p[find(a)] = find(b); //b的根节点作为a的根节点的父节

}

Q: if(find(a) == find(b)) return Yes;

else return No;

巴特西

day1 AcWing 836. 合并集合

最新文章

热门文章