LeetCode 刷题笔记——并查集

前言

上一篇博客中完成了并查集的学习，仅仅学个理论基础肯定是不够的，因此针对并查集继续进行同步练习，依旧在 LeetCode 平台刷题，并记录在此。

128. 最长连续序列

难度：中等

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

1
2
3
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

1
2
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

解题思路

既然训练并查集，当然首先考虑能否用并查集解题。题目要求查找最长的连续序列，那么我们就可以认为，相邻的两个数 相连 ，那最长的连续序列其实就相当于求并查集中的最大连通分量。我们可以先列出之前完成的并查集的 API 表：

API备注
void union_find(int N)初始化
void union(int p, int q)连接 p, q
int find(int p)返回标识
boolean connected(int p, int q)判断 p, q 是否相连

需要解决的第一个问题是，我们的并查集内的初始序列是一串连续且从 0 开始的整数，如何将这样的序列一一映射到我们输入的随机排列的序列呢？一个简单的思路是将输入的序列存放在并查集算法以外的数组里，这样在并查集算法中的内部序列其实就是外部随机序列所对应的索引，我们只需把连续的两个数的索引传给 union() 方法即可。

那么第二个问题就来了，现在我们可以完成连通分量的划分，但是我们并没有计算连通分量中元素个数的方法。为此我们有必要使用一个辅助数组用来存储连通分量中的元素个数，并增加一个返回最大个数值的方法，我们称之为 GetMax() 。

具体实现

存储连通分量的元素数量的数组应该如何实现呢？还记得在并查集算法中，我们为了提升性能引入了一个辅助数组 sz[] ，里面存储的就是当前连通分量的元素数量（因为我们需要总是将较小分量连接到较大分量）。因此，直接使用 GetMax() 方法返回数组 sz[] 中的最大元素即可，当然，当输入序列的长度小于 2 的话，我们只需返回序列长度值即可（在入口处直接判断即可）。实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int longestConsecutive(int[] nums) {
    //在 Solution 类中！
    int N = nums.length;
	if (N < 2)
    	return N;
}

public int GetMax() {
    //在 union_find 类中！
    int max = 0;
    for(int i = 0; i < sz.length; i++)
        max = Math.max(max, sz[i]);
    return max;
}

不过，这样就必须额外遍历一遍 sz[] 数组了，其实我们可以新增一个内部变量 M 用来存储最大元素数量，而将更新 M 的操作放在我们更新 sz[] 数组的同时，这样，就不要在调用 GetMax() 方法时进行额外的遍历了，且时间复杂度也低于完整遍历。值得注意的是，M 的初始值应为1，因为如果程序运行过程中不创建新连接时，即不调用 union() 方法时，M 值将不会更新，而此时 M 值应为1（M 当且仅当输入序列为空时值为零，这种情况已由程序入口处判断长度语句过滤）。实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int M = 1;
public void union(int p, int q) {
    int pRoot = find(p);
    int qRoot = find(q);
    if (sz[pRoot] < sz[qRoot]) {
        id[pRoot] = qRoot;
        sz[qRoot] += sz[pRoot];
        M = Math.max(M, sz[qRoot]);
    } else {
        id[qRoot] = pRoot;
        sz[pRoot] += sz[qRoot];
        M = Math.max(M, sz[pRoot]);
    }
}
public int GetMax() {
    return M;
}

那么接下来要解决的，就是如何将值相邻的两个数提取出来并传给 union() 方法。不考虑性能的话，直接遍历完全可以解决，即取其中一个数，然后再遍历寻找与他相邻的数。但是，这样显然过于粗鲁。当我们取一个数的时候，其实我们就已经知道与他相邻的唯二可能值了，因此我们需要的只是已知值的索引而已。而要满足这个需求，我们可以直接使用哈希表。每次取一个值并判断相邻元素是否存在，若存在则传给 union() 方法。实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int longestConsecutive(int[] nums) {
    Map<Integer, Integer> m = new HashMap<>();
    int N = nums.length;
    if (N < 2)
        return N;
    union_find uf = new union_find(N);
    for (int i = 0; i < N; i++) {
        if (m.containsKey(nums[i])) continue;
        if (m.containsKey(nums[i] - 1)) 
            uf.union(i, m.get(nums[i] - 1));
        if (m.containsKey(nums[i] + 1)) 
            uf.union(i, m.get(nums[i] + 1));
        m.put(nums[i], i);
    }
    return uf.GetMax();
}

以上，我们就成功使用并查集解决了这道问题，源代码与其他语言实现在下方给出。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> m = new HashMap<>();
        int N = nums.length;
        if (N < 2)
            return N;
        union_find uf = new union_find(N);
        for (int i = 0; i < N; i++) {
            if (m.containsKey(nums[i])) continue;
            if (m.containsKey(nums[i] - 1)) 
                uf.union(i, m.get(nums[i] - 1));
            if (m.containsKey(nums[i] + 1)) 
                uf.union(i, m.get(nums[i] + 1));
            m.put(nums[i], i);
        }
        return uf.GetMax();
    }
}

class union_find {
    private int[] id;
    private int[] sz;
    private int M = 1;
    public union_find(int N) {
        id = new int[N];
        sz = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }
    public int find(int p) {
        int tmp = p;
        while (p != id[p]) p = id[p];
        while (tmp != id[tmp]) {
            int t = tmp;
            tmp = id[tmp];
            id[t] = p;
        }
        return p;
    }
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (sz[pRoot] < sz[qRoot]) {
            id[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
            M = Math.max(M, sz[qRoot]);
        } else {
            id[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
            M = Math.max(M, sz[pRoot]);
        }
    }
    public int GetMax() {
        return M;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# 小白尝试，代码简陋，不做参考
# 会改的会改的

class quick_union:
    def __init__(self, N):
        self.id = list(range(N))
        self.sz = [1]*N
        self.M = 1

    def connected(self, p, q):
        return self.find(p) == self.find(q)

    def find(self, p):
        while p != self.id[p]:
            p = self.id[p]
        while tmp != self.id[tmp]:
            t = tmp
            tmp = self.id[tmp]
            self.id[t] = p
        return p

    def union(self, p, q):
        pR = self.find(p)
        qR = self.find(q)
        if self.sz[pR] < self.sz[qR]:
            self.id[pR] = qR
            self.sz[qR] += self.sz[pR]
            self.M = max(self.M, self.sz[qR])
        else:
            self.id[qR] = pR
            self.sz[pR] += self.sz[qR]
            self.M = max(self.M, self.sz[pR])

    def GetMax(self):
        return self.M


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        d = {}
        N = len(nums)
        if N < 2:
            return N
        qu = quick_union(N)
        for i in range(N):
            if nums[i] in d.keys():
                continue
            if nums[i] - 1 in d.keys():
                qu.union(i, d[nums[i] - 1])
            if nums[i] + 1 in d.keys():
                qu.union(i, d[nums[i] + 1])
            d[nums[i]] = i
        return qu.GetMax()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class union_find {
private:
	int* id;
	int* sz;
	int M = 1;
public:
	union_find(int N) {
		id = new int[N];
		sz = new int[N];
		for (int i = 0; i < N; i++) {
			id[i] = i;
			sz[i] = 1;
		}
	}
	~union_find();
	int find(int p) {
		int tem = p;
		while (p != id[p]) p = id[p];
		while (tem != id[tem]) {
			int t = tem;
			tem = id[tem];
			id[t] = p;
		}
		return p;
	}
	bool connected(int p, int q) {
		return find(p) == find(q);
	}
	void Union(int p, int q) {
		int qRoot = find(q);
		int pRoot = find(p);
		if (sz[pRoot] < sz[qRoot]) {
			id[pRoot] = qRoot;
			sz[qRoot] += sz[pRoot];
            M = max(M, sz[qRoot]);
		}
		else {
			id[qRoot] = pRoot;
			sz[pRoot] += sz[qRoot];
            M = max(M, sz[pRoot]);
		}
	}

	int GetMax() {
		return M;
	}
};
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
		unordered_map<int, int> um;
		long N = nums.size();
        if (N < 2)
            return N;
		union_find* uf = new union_find(N);
		for (int i = 0; i < N; i++) {
			if (um.count(nums[i])) continue;
			if (um.count(nums[i] - 1)) 
				uf->Union(i, um.at(nums[i] - 1));
			if (um.count(nums[i] + 1))
				uf->Union(i, um.at(nums[i] + 1));
			um.insert(pair<int, int>(nums[i], i));
		}
		return uf->GetMax();
    }
};

但是

但是这道题目，真的必须搞这么麻烦吗？

也许引入并查集将连续的序列划分为同一连通分量是一种最简单直接的想法，但是我们创建并查集的过程，却需要另外引入哈希表才能相对高效地完成创建操作。既然哈希表就能完成高效地查找，那我们通过不断查找一个数的相邻数是否存在并同时计数，最后得到的最大数不就是我们需要的答案了吗。

当然这里仅提供一种思路，具体的优化实现就放在哈希表的训练内容中。

130. 被围绕的区域

难度：中等

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例 1：

1
2
3
输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2：

1
2
输入：board = [["X"]]
输出：[["X"]]

提示：

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] 为 'X' 或 'O'

解题思路

题目中解释表明只有边界上的 'O' 及与其相连的 'O' 不会改变，因此我们可以将题目考虑为寻找不与边界相连的 'O' 并将它改为 'X' ，使用并查集即正好将所有与边界相连的 'O' 作为一个连通分量，最后将所有不在该分量内的 'O' 修改为 'X' 即可。

首先，第一个问题在于如何将所有与边界相连的 'O' 放入一个连通分量，边界上可能会有多个 'O' ，对于不在边界上的 'O' ，我们只能判断它是否与某一边界上的 'O' 相连，最后得到基于边界上不同 'O' 的多个连通分量，这将极大复杂化程序，因此我们必须让所有符合条件的 'O' 存在于同一连通分量中。我们可以在并查集中额外放置一个元素，首先我们遍历边界，将边界上的 'O' 全部与这个元素相连，然后再遍历内部将与边界相连的元素也连接到这个连通分量，最后我们就可以得到符合条件的一整个连通分量。

第二个问题是如何在并查集中表示这些矩阵元素，这些矩阵都存储在二维数组中，而使用二维坐标进行并查集相关操作显然是非常复杂的，即使可以实现也不值得去实现。由于矩阵的各性质我们可以获得，因此我们可以将矩阵的二维坐标转换为一维坐标。

具体实现

首先为了完成坐标的转换，定义一个 Convert() 方法，二维坐标到一维坐标的转换需要我们已知三个参数，即二维坐标值 (x , y) 与矩阵宽度 w，满足 A[x][y]=A[x * w + y] 。具体实现如下：

1
2
3
4
int Convert(int x, int y, int w) {
	//x、y 表示二维坐标值，w 表示矩阵宽度。
	return x * w + y;
}

然后进行并查集操作，首先初始化并查集，大小为矩阵的大小加一，多的那一个用来作为所有边界节点的父节点，我们称他为“祖宗节点”，他将与所有边界上的 'O' 相连，实现如下：

1
2
3
4
5
int len = board.length;  // 矩阵行数
int wid = board[0].length;  // 矩阵列数，即第一行元素数
int boardSize = len * wid;  // 矩阵大小（元素个数）
union_find uf = new union_find(boardSize + 1);
// 初始化并查集，大小为矩阵大小+1

接下来就要遍历边界，将边界中的 'O' 先与“祖宗节点”相连。矩阵坐标是从 1 开始的，因此我们令并查集中的最大元素作为“祖宗节点”，即 boardSize 。由于在遍历的同时需要判断元素是否为 'O' ，因此需要两层 for 循环以二维坐标遍历矩阵。但是我们并不需要遍历整个矩阵，除了首尾两行，其他行我们遍历首尾两个元素即可。

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 0; i < len; i++) {
	for (int j = 0; j < wid; ) {
		if (board[i][j] == 'O')
			uf.union(Convert(i, j, wid), boardSize);
        	// 当元素为 O 时将其与“祖宗节点”相连
		if (i == 0 || i == len - 1 || j != 0)
			j++;
		else
			j = wid - 1;
        	// 当不在首尾行且位于行首时，直接跳到行尾
	}
}

接下来遍历非边界矩阵元素，如何判断元素是否与边界相连呢，其实不用判断，我们只需将每个元素与其周围的相同元素相连即可，因为最后我们只要判断矩阵中的 'O' 是否与“祖宗节点”相连即可，这也正是我们使用并查集的原因。因此，本次遍历我们将遍历每一个元素，如果为 'O' ，则将它与周围的 'O' 相连，此外，无需遍历边界。实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
 * 有趣的是，本段程序原本并没有在创建新连接之前判断两节点是否
 * 已经相连，而且运行时也并没有报错，但是在用 c++ 实现的过程
 * 中就发现 sz[] 数组爆栈了，原因就是重复创建连接会导致 sz[]
 * 数组中的值翻倍。
 * 然而这实际上应该在 union() 函数中完成，当时我觉得 union()
 * 函数的调用应该基于不相连，事实证明，永远不要让函数的实现基
 * 于信任！
 * 本程序选择在 if 中进行判断，对并查集的修改于 Python 与
 * c++ 中展示。
 */
for (int i = 1; i < len - 1; i++) {
    for (int j = 1; j < wid - 1; j++) {
        // i、j 均跳过首尾，从而跳过边界
        if (board[i][j] == 'O') {
            int index = Convert(i, j, wid);
            if (board[i - 1][j] == 'O' && !uf.connected(Convert(i - 1, j, wid), index))
                uf.union(Convert(i - 1, j, wid), index);
            if (board[i + 1][j] == 'O' && !uf.connected(Convert(i + 1, j, wid), index))
                uf.union(Convert(i + 1, j, wid), index);
            if (board[i][j + 1] == 'O' && !uf.connected(Convert(i, j + 1, wid), index))
                uf.union(Convert(i, j + 1, wid), index);
            if (board[i][j - 1] == 'O'  && !uf.connected(Convert(i, j - 1, wid), index))
                uf.union(Convert(i, j - 1, wid), index);
        }
    }
}

完成了上述操作之后，所有符合条件的 'O' 都与“祖宗节点”处于同一连通分量，因此，我们最后遍历一遍矩阵，将不与“祖宗节点”相连的 'O' 全部修改为 'X' ，任务就完成了！当然，这次依然不用遍历边界，毕竟在边界的 'O' 一定与“祖宗节点”相连。实现如下：

1
2
3
4
5
6
7
for (int i = 1; i < len - 1; i++) {
	for (int j = 1; j < wid - 1; j++) {
		if (board[i][j] == 'O' && !uf.connected(Convert(i, j, wid), boardSize))
            // 当 'O' 与“祖宗节点”不相连时则修改
			board[i][j] = 'X';
	}
}

至此，我们就完成了各部分的实现，只需整合一下即可完成本题，完整源代码及其他语言实现将由下方给出。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
class Solution {
    int Convert(int x, int y, int w) {
        //x、y 表示二维坐标值，w 表示矩阵宽度。
        return x * w + y;
    }
    public void solve(char[][] board) {
        int len = board.length;  // 矩阵行数
        int wid = board[0].length;  // 矩阵列数，即第一行元素数
        int boardSize = len * wid;  // 矩阵大小（元素个数）
        union_find uf = new union_find(boardSize + 1);
        // 初始化并查集，大小为矩阵大小+1

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < wid; ) {
                if (board[i][j] == 'O')
                    uf.union(Convert(i, j, wid), boardSize);
                    // 当元素为 O 时将其与“祖宗节点”相连
                if (i == 0 || i == len - 1 || j != 0)
                    j++;
                else
                    j = wid - 1;
                    // 当不在首尾行且位于行首时，直接跳到行尾
            }
        }

        
/*
 * 有趣的是，本段程序原本并没有在创建新连接之前判断两节点是否
 * 已经相连，而且运行时也并没有报错，但是在用 c++ 实现的过程
 * 中就发现 sz[] 数组爆栈了，原因就是重复创建连接会导致 sz[]
 * 数组中的值翻倍。
 * 然而这实际上应该在 union() 函数中完成，当时我觉得 union()
 * 函数的调用应该基于不相连，事实证明，永远不要让函数的实现基
 * 于信任！
 * 本程序选择在 if 中进行判断，对并查集的修改于 Python 与
 * c++ 中展示。
 */
        for (int i = 1; i < len - 1; i++) {
            for (int j = 1; j < wid - 1; j++) {
            // i、j 均跳过首尾，从而跳过边界
                if (board[i][j] == 'O') {
                    int index = Convert(i, j, wid);
                    if (board[i - 1][j] == 'O' && !uf.connected(Convert(i - 1, j, wid), index))
                        uf.union(Convert(i - 1, j, wid), index);
                    if (board[i + 1][j] == 'O' && !uf.connected(Convert(i + 1, j, wid), index))
                        uf.union(Convert(i + 1, j, wid), index);
                    if (board[i][j + 1] == 'O' && !uf.connected(Convert(i, j + 1, wid), index))
                        uf.union(Convert(i, j + 1, wid), index);
                    if (board[i][j - 1] == 'O'  && !uf.connected(Convert(i, j - 1, wid), index))
                        uf.union(Convert(i, j - 1, wid), index);
                }
            }
        }

        for (int i = 1; i < len - 1; i++) {
            for (int j = 1; j < wid - 1; j++) {
                if (board[i][j] == 'O' && !uf.connected(Convert(i, j, wid), boardSize))
                    board[i][j] = 'X';
            }
        }
    }
}

public class union_find {
    private int[] id;
    private int[] sz;
    public union_find(int N) {
        id = new int[N];
        sz = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }
    public int find(int p) {
        int tmp = p;
        while (p != id[p]) p = id[p];
        while (tmp != id[tmp]) {
            int t = tmp;
            tmp = id[tmp];
            id[t] = p;
        }
        return p;
    }
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (sz[pRoot] < sz[qRoot]) {
            id[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        } else {
            id[qRoot] = pRoot;
            sz[pRoot] += sz[pRoot];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class quick_union:
    def __init__(self, N):
        self.id = list(range(N))
        self.sz = [1] *N

    def connected(self, p, q):
        return self.find(p) == self.find(q)

    def find(self, p):
        tmp = p
        while p != self.id[p]:
            p = self.id[p]
        while tmp != self.id[tmp]:
            t = tmp
            tmp = self.id[tmp]
            self.id[t] = p
        return p

    def union(self, p, q):
        pR = self.find(p)
        qR = self.find(q)
        # 若已经相连则不再创建连接
        if pR == qR:
            return
        if self.sz[pR] < self.sz[qR]:
            self.id[pR] = qR
            self.sz[qR] += self.sz[pR]
        else:
            self.id[qR] = pR
            self.sz[pR] += self.sz[qR]

class Solution:
    def Convert(self, x, y, w):
        return x * w + y
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        Len = len(board)
        wid = len(board[0])
        boardSize = Len * wid
        qu = quick_union(boardSize + 1)

        for i in range(Len):
            j = 0
            while j < wid:
                if board[i][j] == 'O':
                    qu.union(self.Convert(i, j, wid), boardSize)
                if i == 0 or i == Len - 1 or j != 0:
                    j += 1
                else:
                    j = wid - 1
        
        for i in range(1, Len - 1):
            for j in range(1, wid - 1):
                if board[i][j] == 'O':
                    index = self.Convert(i, j, wid)
                    if board[i - 1][j] == 'O':
                        qu.union(self.Convert(i - 1, j, wid), index)
                    if board[i + 1][j] == 'O':
                        qu.union(self.Convert(i + 1, j, wid), index)
                    if board[i][j - 1] == 'O':
                        qu.union(self.Convert(i, j - 1, wid), index)
                    if board[i][j + 1] == 'O':
                        qu.union(self.Convert(i, j + 1, wid), index)
        
        for i in range(1, Len - 1):
            for j in range(1, wid - 1):
                if board[i][j] == 'O' and (not qu.connected(self.Convert(i, j, wid), boardSize)):
                    board[i][j] = 'X'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
class union_find {
private:
    int * id;
    int * sz;
public:
    union_find(int N) {
        id = new int[N];
        sz = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }
    ~union_find() {}

    int find(int p) {
        int tmp = p;
        while (p != id[p])
            p = id[p];
        while (tmp != id[tmp]) {
            int t = tmp;
            tmp = id[tmp];
            id[t] = p;
        }
        return p;
    }

    bool connected(int p, int q) {
        return find(p) == find(q);
    }

    void Union(int p, int q) {
        int pR = find(p);
        int qR = find(q);
        if (pR == qR)
            return;
        if (sz[pR] < sz[qR]) {
            id[pR] = qR;
            sz[qR] += sz[pR];
        } else {
            id[qR] = pR;
            sz[pR] += sz[qR];
        }
    }
};

class Solution {
public:
    int Convert(int x, int y, int w) {
        return x * w + y;
    }

    void solve(vector<vector<char>>& board) {
        int len = board.size();
        int wid = board[0].size();
        int boardSize = len * wid;
        union_find * uf = new union_find(boardSize + 1);
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < wid;) {
                if (board[i][j] == 'O')
                    uf->Union(Convert(i, j, wid), boardSize);
                if (i == 0 || i == len - 1 || j != 0)
                    j++;
                else
                    j = wid - 1;
            }
        }

        for (int i = 1; i < len - 1; i++) {
            for (int j = 1; j < wid - 1; j++) {
                if (board[i][j] == 'O') {
                    int index = Convert(i, j, wid);
                    if (board[i - 1][j] == 'O')
                        uf->Union(Convert(i - 1, j, wid), index);
                    if (board[i + 1][j] == 'O')
                        uf->Union(Convert(i + 1, j, wid), index);
                    if (board[i][j - 1] == 'O')
                        uf->Union(Convert(i, j - 1, wid), index);
                    if (board[i][j + 1] == 'O')
                        uf->Union(Convert(i, j + 1, wid), index);
                }
            }
        }

        for (int i = 1; i < len - 1; i++) {
            for (int j = 1; j < wid - 1; j++)
                if (board[i][j] == 'O' && !uf->connected(Convert(i , j, wid), boardSize))
                    board[i][j] = 'X';
        }
    }
};