并查集
并查集主要用于判断图的联通性以及判环等问题的解决。
并查集的定义
父数组，保存当前下标对应的父节点编号。
find（查找祖先节点）操作 寻找父节点，（在此过程中将并查集树压平）
union （合并操作 联通两个点所在的集合）
例题 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1:
输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1
示例 2:
输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
using namespace std;
#include<iostream>
#include<vector>
#include<unordered_set>int parent[250001];int find(int x){ //查找父节点，并且将路径压缩if(x!=parent[x]){parent[x]=find(parent[x]);}return parent[x];}bool Union(int x,int y){ //合并两个子集int dx=find(x);int dy=find(y);if(dx==dy){return true;}if(dx>dy){parent[dx]=dy;}else{parent[dy]=dx;}return false;}int numIslands(vector<vector<char>>& grid) {int rlen=grid.size();if(rlen==0){return 0;}int clen=grid[0].size();for(int i=0;i<rlen*clen;i++){parent[i]=i;}for(int i=0;i<rlen;i++){for(int j=0;j<clen;j++){if(grid[i][j]=='1'){if(i+1<rlen&&grid[i+1][j]=='1'){Union(i*clen+j,(i+1)*clen+j);}if(j+1<clen&&grid[i][j+1]=='1'){Union(i*clen+j,i*clen+j+1);}}}}for(int i=0;i<rlen*clen;i++){cout<<find(i)<<endl;}unordered_set<int> us;for(int i=0;i<rlen;i++){for(int j=0;j<clen;j++){if(grid[i][j]=='1'){cout<<find(i*rlen+j)<<endl;us.insert(find(i*rlen+j));}}}return us.size();}
int main(){int rlen; //输入行输 int clen;//输入列数cin>>rlen>>clen;vector<char> temp(clen,'0');vector<vector<char>> grid(rlen,temp);for(int i=0;i<rlen;i++){for(int j=0;j<clen;j++){cin>>grid[i][j];}} cout<<numIslands(grid)<<endl; }