居然可以这样并(并是什么结构)

并查集是一种树状的数据结构,经常用于解决组团和配对问题，比如解决朋友圈问题，可以高效的对数据集进行分组合并。查询的最坏情况时间复杂度是O(n),

并查集是一种树状的数据结构,经常用于解决组团和配对问题，比如解决朋友圈问题，可以高效的对数据集进行分组合并查询的最坏情况时间复杂度是O(n),平均时间复杂度是O(logN)，结合路径压缩可以进一步降低时间复杂度，而且并查集的实现比较简单，便于理解。

并查集的实现主要包括三个部分：(1) 构建并查集(2) 并查集的合并(3) 查询根节点1. 并查集初始化满足parent[i]=i的就是根元素

private int[] parent; private int count; public void Init(int n) { parent=new parent[n]; count=n; for(int i=0;i

2.并查集的合并

public void Union(int x,int y) { var rootX=Find(x); var rootY=Find(y); if(rootX==rootY) { return ; } parent[rootY]= rootX; count--; }

3.并查集查询

//并查集查询，并对路径进行压缩 public int Find(i) { while(i!=parent[i]) { //路径压缩 parent[i]=parent[parent[i]]; //继续遍历父节点 i=parent[i] } }。

4.应用Demo(岛屿数量问题)问题描述：给你一个由 1（陆地）和 0（水）组成的的二维网格，请你计算网格中岛屿的数量岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成此外，你可以假设该网格的四条边均被水包围。

首先这个问题解决思路有很多，此处使用并查集的思路解决可以将每个陆地或者水初始化为一个并查集然后对相邻的陆地进行并查集的合并，最后剩余的并查集的数量就是答案public class Solution { public int NumIslands(char[][] grid) { var row = grid.Length; var col= grid[0].Length; if (grid.Length == 0 || grid[0].Length == 0) { return 0; } var us = new UnionSet(); us.Init(row*col); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (grid[i][j] == 1) { if (j < col - 1 && grid[i][j + 1] ==1) { us.Union(i*col + j, i * col + (j + 1)); } if (i < row - 1 && grid[i+1][j]==1) { us.Union(i * col + j, (i+1) * col + j); } } else { us.count--; } } } return us.GetUnionCount(); } } public class UnionSet { private int[] parent; public int count; public void Init(int n) { parent = new int[n]; for (int i = 0; i < n; i++) { parent[i] =i; } count = n; } public int Find(int p) { while (p != parent[p]) { parent[p] = parent[parent[p]]; p = parent[p]; } return p; } public void Union(int x, int y) { var rootX = Find(x); var rootY = Find(y); if (rootX == rootY) { return; } parent[rootY]=x; count--; } public int GetUnionCount() { return count; } }。