如何运用并查集算法解决特定问题？

本文共计564个文字，预计阅读时间需要3分钟。

作者：Grey原文地址：使用并查集解决的相关问题及关于并查集的说明，详见如下博客：+ 使用并查集处理集合的合并和查询问题，相关问题目录LeetCode 200. 岛屿数量，本题的解题思路参考博客：+ 使用并查集处理集合的合并和查询问题，相关问题目录LeetCode 200. 岛屿数量，本题的解题思路参考博客：

作者: Grey

原文地址：使用并查集解决的相关问题

关于并查集的说明，见如下博客：

使用并查集处理集合的合并和查询问题

相关题目 LeetCode 200. 岛屿数量

本题的解题思路参考博客

使用DFS和并查集方法解决岛问题

LeetCode 547. 省份数量

主要思路

横纵坐标表示的是城市，因为城市是一样的，所以只需要遍历对角线上半区或者下半区即可，如果某个(i,j)位置是1，可以说明如下两个情况

第一，i这座城市和j这座城市可以做union操作。

第二，(j,i)位置一定也是1。

遍历完毕后，返回整个并查集中的集合数量即可。