并查集并查集

并查集就是一个一群人找祖宗的过程：

最开始，每个人就是一个单独的部落，

根据某个条件判断他俩属于一个部落，比如他俩相似，或者有其它属性，

属于一个部落的两个人，就有一个祖宗，

找到同宗的，那就部落合并，最开始的部落数就可以-1了

遍历到最后的最后，所有人都认祖归宗，那么部落数就是最后的结果

上面这个题也可以使用图的联通分量做

将strs这个数组中string的相似关系画成一张图，再根据广度优先遍历方法去遍历这个图。在遍历的过程中，每次遇到没有遍历过的node，就意味着开辟了一个新部落，此时cnt++。

最终遍历完所有的string时，cnt是多少就证明有多少个新部落

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34618 人正在系统学习中

来源：普通网友