并查集的思想是用一个数组表示了整片森林#xff08;parent#xff09;#xff0c;树的根节点唯一标识了一个集合#xff0c;我们只要找到了某个元素的的树根#xff0c;…一、并查集概念

并查集是一种树型的数据结构用于处理一些不相交集合的合并及查询问题。

并查集的思想是用一个数组表示了整片森林parent树的根节点唯一标识了一个集合我们只要找到了某个元素的的树根就能确定它在哪个集合里。

【摘自菜鸟教程】

大家看剧都知道古时候基本上都会拉帮结派形成大大小小许多帮派。

这些帮派都会有等级划分大当家二当家等等。

类似于这样的结构。

假如三当家的小弟想知道他真正的老大是谁那么他就去问三当家三当家就告诉他他的老大是二当家然后这个小弟就去问二当家二当家就会告诉他他的老大是大当家那么小弟再去问大当家大当家就会告诉他我才是你真正的老大。

那么所有这些人他们的老大都只有一个那就是“大当家”。

翻译成大白话说就是如果一个元素的老大不是他自己那么他自己的老大的老大就是他的老大。

假如突然有一天大当家干掉了自己的死对头另一个帮派的老大并成功吞并了他的帮派。

那么现在另一个帮派的小弟再找大哥时就会发现此时自己的大哥已经变成了另一个帮派的大哥。

这就是“并查集”中“并”的部分。

二、并查集在算法题中应用

isConnected[i].lengthisConnected[i][j]

0isConnected[i][i]

简单分析题目后发现这就是一个找大哥的过程。

每一个省份算作一个帮派有几个“大哥”就是有几个省份所以该题可以使用并查集。

直接上代码

“并”的过程i城市的大哥就是j城市的大哥city[find(i,

city)]