有关并查集的一道编程题

题目来自牛客网：
https://www.nowcoder.com/practice/1ecd3d9e09664cde94919b65ea06b47c?tpId=90&tqId=30919&tPage=8&rp=8&ru=/ta/2018test&qru=/ta/2018test/question-ranking


通过讨论区知道这道题使用并查集来解决的（用传统的bfs或者dfs复杂度太高），由于自己并不知道并查集是什么，于是百度之，通过这篇文章了解https://blog.****.net/dm_vincent/article/details/7655764，这篇文章讲的非常好，不了解的可以看一下。

因为并查集是用一维数组来表示点与所在集合之间的关系的，所以这里需要一维二维之间的转换。假设二维数组a，一维数组b，那么a[i][j]对应着b[i*n+j]。

先分析一下并查集模板，这个是本题的关键,如果觉得不理解可以去看我推荐的博客：

    //两个数组，par代表所在的组，rank代表组的排名，其实就是组元素的多少的一个表示
    //这里rank中的值并不是具体值，只是代表一个排名，这就够用了，通过这个信息，我们知道
    //在合并时应该往哪一个组里面合并，往较大的组里合并，保证平衡性
    static int[] par, rank;

    //查找x所属的组，如果x不是根，一边往上查找一边缩小层数
	static int find(int x) {
		return x == par[x] ? x : (par[x] = find(par[x]));
	}

    //将x所属的组和y所属的组这两个组合并为一组，这里需要先找到根，再比较rank的大小
    //把rank较小的组连接到rank较大的组下面
	static void union(int x, int y) {
		if ((x = find(x)) == (y = find(y)))
			return;
		if (rank[x] < rank[y]) {
			par[x] = y;
		} else {
			par[y] = x;
			if (rank[x] == rank[y])
				rank[x]++;
		}
	}
    //判断x和y是否属于同一个组
	static boolean same(int x, int y) {
		return find(x) == find(y);
	}

下面上整道题的代码：

import java.util.*;

public class Solution144 {

	static final int[][] dir = { { 1, -1, 0, 0 }, { 0, 0, 1, -1 } };

	static int[] par, rank;

	static int find(int x) {
		return x == par[x] ? x : (par[x] = find(par[x]));
	}

	static void union(int x, int y) {
		if ((x = find(x)) == (y = find(y))) {
			return;
		}
		if (rank[x] < rank[y]) {
			par[x] = par[y];
		} else {
			par[y] = par[x];
			if (rank[x] == rank[y]) {
				rank[x]++;
			}
		}
	}

	static boolean same(int x, int y) {
		return find(x) == find(y);
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int m = scanner.nextInt();
			int n = scanner.nextInt();
			int k = scanner.nextInt();
			//需要加1保证par[0] = 0
			par = new int[m * n + 1];
			rank = new int[m * n + 1];
			int count = 0;
			StringBuilder res = new StringBuilder("");
			while (k-- > 0) {
				int r = scanner.nextInt();
				int c = scanner.nextInt();
				int x = r * n + c + 1;
				if (r >= 0 && r < m && c >= 0 && c < n && find(x) == 0) {
					par[x] = x;
					count++;
					for (int i = 0; i < 4; i++) {
						int rr = r + dir[0][i];
						int cc = c + dir[1][i];
						int y = rr * n + cc + 1;
						//如果相邻的点不是水且与当前的点不属于同一个组，那么把他们联合，并将count减1
						if (rr >= 0 && rr < m && cc >= 0 && cc < n && find(y) != 0 && !same(x, y)) {
							union(x, y);
							count--;
						}
					}

				}
				res.append(count);
				if (k > 0) {
					res.append(" ");
				}

			}
			System.out.println(res);
		}
		scanner.close();

	}

}

运行结果如下：