【LC总结】Union Find系列(Num of Islands I&II/Graph Valid Tree/etc) - Road to Glory - SegmentFault 思否

【LC总结】Union Find系列(Num of Islands I&II/Graph Valid Tree/etc) - Road to Glory - SegmentFault 思否

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X X O O X X X O X X O X X 

After running your function, the board should be:

X X X X X X X X X X X X X O X X 

Note

不得不说，对于这道题而言，Union Find是一种很木讷的模板。

主函数：按矩阵大小建立：

1. 一个UnionFind类进行后续操作；

2. 一个dummy结点用来连接边角不可能被X围绕的O；

3. 一个node()函数对矩阵元素进行结点线性化。

操作：

1. 遍历所有结点，矩阵边角的O与dummy相连，矩阵内部的O与相邻的O相连；

2. 遍历所有结点，与dummy相连的结点设置为O，其它所有结点设置为X。

UnionFind函数：建立：

1. 全局变量parents；

2. 初始化函数UnionFind(int size)；

3. 查找parents函数find(int node)；

4. 归并函数union(int node1, int node2)；

5. 测试两结点是否相连函数isConnected(int node1, int node2)；

操作：

1. find(int node): 用while循环向上查找node的parent，注意先向上迭代parents[node]，再迭代node，否则会超时；

2. union(int node1, int node2): 找到两个结点的parents，r1和r2，令parents[r1] = r2；

3. isConnected(int n1, int n2): 查看两个结点的parents是否相等。

Read full article from 【LC总结】Union Find系列(Num of Islands I&II/Graph Valid Tree/etc) - Road to Glory - SegmentFault 思否