链接：https://leetcode.com/tag/union-find/
【128】Longest Consecutive Sequence （2018年11月22日，开始解决hard题）
给了一个无序的数组，问这个数组里面的元素（可以重新排序）能组成的最长的连续子序列是多长。本题的时间复杂度要求是 O(N).
本题 array 专题里面有， 链接：https://www.cnblogs.com/zhangwanying/p/9610923.html ，用个 hashmap 可以做到 O(N).
本题用 union-find 怎么解，不知道 orz。
【130】Surrounded Regions （2019年1月31日，UF专题）
给了个二维 grid，把里面 O 全部变成 X，但是 边界和边界联通区域内的 O 保留。
题解：我以前是用dfs解的。今天看了discuss高票使用UF，学习了一下。我们把边界上的 O 和边界联通区域内的 O 的坐标与一个 dummy node 联通就好了。然后遍历 grid，如果坐标与 dummy node 坐标联通，就保留成 O，不然改成 X
1 class UF {
2 public:
3 UF(int size) {
4 father.resize(size);
5 rank.resize(size, 0);
6 for (int i = 0; i < size; ++i) {
7 father[i] = i;
8 }
9 }
10 int find(int x) {
11 return x == father[x] ? x : father[x] = find(father[x]);
12 }
13 void connect(int x, int y) {
14 int xx = find(x), yy = find(y);
15 if (xx == yy) { return; }
16 if (yy > xx) {
17 father[xx] = yy;
18 } else {
19 father[yy] = x;
20 }
21 }
22 vector<int> father;
23 vector<int> rank;
24 };
25 class Solution {
26 public:
27 void solve(vector<vector<char>>& board) {
28 if (board.empty() || board[0].empty()) { return; }
29 const int n = board.size(), m = board[0].size();
30 UF uf(n * m + 1);
31 for (int i = 0; i < n; ++i) {
32 for (int j = 0; j < m; ++j) {
33 if (board[i][j] == 'O') {
34 if ((i == 0 || i == n-1 || j == 0 || j == m-1)) {
35 uf.connect(i * m + j, n * m);
36 } else {
37 if (board[i-1][j] == 'O') {
38 uf.connect(i * m + j, (i-1) * m + j);
39 }
40 if (board[i+1][j] == 'O') {
41 uf.connect(i * m + j, (i+1) * m + j);
42 }
43 if (board[i][j-1] == 'O') {
44 uf.connect(i * m + j, i * m + j - 1);
45 }
46 if (board[i][j+1] == 'O') {
47 uf.connect(i * m + j, i * m + j + 1);
48 }
49 }
50 }
51 }
52 }
53 for (int i = 0; i < n; ++i) {
54 for (int j = 0; j < m; ++j) {
55 if (uf.find(i * m +j) != n * m) {
56 board[i][j] = 'X';
57 }
58 }
59 }
60 return;
61 }
62 };
View Code
【200】Number of Islands （2019年1月31日，UF专题）
给了一个二维的grid，0 代表海， 1 的联通块代表岛屿，问有多少岛屿。
题解：和130题一样的想法。判断当前结点和上下左右四个结点是不是都是1，如果是的话，就联通这两个点。
1 class UF {
2 public:
3 UF(int size) {
4 father.resize(size);
5 rank.resize(size, 0);
6 for (int i = 0; i < size; ++i) {
7 father[i] = i;
8 }
9 }
10 int find(int x) {
11 return x == father[x] ? x : father[x] = find(father[x]);
12 }
13 void connect(int x, int y) {
14 int xx = find(x), yy = find(y);
15 if (xx == yy) { return; }
16 if (yy < xx) {
17 father[xx] = yy;
18 } else {
19 father[yy] = xx;
20 }
21 }
22 vector<int> father;
23 vector<int> rank;
24 };
25 class Solution {
26 public:
27 int numIslands(vector<vector<char>>& grid) {
28 if (grid.size() == 0 || grid[0].size() == 0) {
29 return 0;
30 }
31 const int n = grid.size(), m = grid[0].size();
32 UF uf(n * m);
33 for (int i = 0; i < n; ++i) {
34 for (int j = 0; j < m; ++j) {
35 int index = i * m + j;
36 if (grid[i][j] == '1') {
37 if (i - 1 >= 0 && grid[i-1][j] == '1') {
38 uf.connect(index, (i-1) * m + j);
39 }
40 if (i + 1 < n && grid[i+1][j] == '1') {
41 uf.connect(index, (i+1) * m + j);
42 }
43 if (j - 1 >= 0 && grid[i][j-1] == '1') {
44 uf.connect(index, i * m + j - 1);
45 }
46 if (j + 1 < m && grid[i][j+1] == '1') {
47 uf.connect(index, i * m + j + 1);
48 }
49 }
50 }
51 }
52 int ret = 0;
53 for (int i = 0; i < n; ++i) {
54 for (int j = 0; j < m; ++j) {
55 int index = i * m + j;
56 if (grid[i][j] == '1' && uf.find(index) == index) {
57 ret++;
58 }
59 }
60 }
61 return ret;
62 }
63 };
View Code
【261】Graph Valid Tree （2019年1月31日，UF专题）
给了 N 个结点 和 一个边的集合，问这个边的集合能不能构成一棵树。
题解：先检查 边集合大小是否等于 N-1， 然后用并查集检查是否有环，没有的话，就是树。
1 class UF {
2 public:
3 UF(int size) {
4 father.resize(size);
5 for (int i = 0; i < size; ++i) {
6 father[i] = i;
7 }
8 }
9 int find (int x) {
10 return x == father[x] ? x : father[x] = find(father[x]);
11 }
12 void connect (int x, int y) {
13 int xx = find(x), yy = find(y);
14 if (xx == yy) { return; }
15 if (xx < yy) {
16 father[yy] = xx;
17 } else {
18 father[xx] = yy;
19 }
20 }
21 vector<int> father;
22 };
23 class Solution {
24 public:
25 bool validTree(int n, vector<pair<int, int>>& edges) {
26 const int edgeSize = edges.size();
27 if (edgeSize != n-1) { return false; } // n 个结点的树有 n-1 条边
28 UF uf(n);
29 for (auto& e: edges) {
30 int u = uf.find(e.first), v = uf.find(e.second);
31 if (u == v) {
32 return false;
33 }
34 uf.connect(e.first, e.second);
35 }
36 return true;
37 }
38 };
View Code
【305】Number of Islands II （2019年1月31日，UF专题）
【323】Number of Connected Components in an Undirected Graph （2019年2月2日，UF tag专题）
给了 n 个结点，编号从 0 到 n-1，以及一个边的集合。问这个无向图里面有多少个联通块。
题解：直接 uf 数联通块。
1 class UF {
2 public:
3 UF(int size) {
4 father.resize(size);
5 for (int i = 0; i < size; ++i) {
6 father[i] = i;
7 }
8 }
9 int find(int x) {
10 return x == father[x] ? x : father[x] = find(father[x]);
11 }
12 void connect(int x, int y) {
13 int xx = find(x), yy = find(y);
14 if (xx == yy) { return; }
15 if (yy < xx) {
16 father[xx] = yy;
17 } else {
18 father[yy] = xx;
19 }
20 }
21 int getCount() {
22 int count = 0;
23 for (int i = 0; i < father.size(); ++i) {
24 if (father[i] == i) {
25 count++;
26 }
27 }
28 return count;
29 }
30 vector<int> father;
31 };
32 class Solution {
33 public:
34 int countComponents(int n, vector<pair<int, int>>& edges) {
35 UF uf(n);
36 for (auto& e : edges) {
37 int u = e.first, v = e.second;
38 uf.connect(u, v);
39 }
40 return uf.getCount();
41 }
42 };
View Code
【547】Friend Circles （2019年2月2日，UF tag专题）
给了一个邻接矩阵, M[i][j] = 1代表 i，j 是朋友关系，我们算上间接朋友关系，问这个矩阵里面一共有几个朋友圈子？
题解：直接用 uf 数这个图里面有多少联通块。
1 class UF {
2 public:
3 UF(int size) {
4 father.resize(size);
5 for (int i = 0; i < size; ++i) {
6 father[i] = i;
7 }
8 }
9 int find(int x) {
10 return x == father[x] ? x : father[x] = find(father[x]);
11 }
12 void connect(int x, int y) {
13 int xx = find(x), yy = find(y);
14 if (xx == yy) { return; }
15 if (yy < xx) {
16 father[xx] = yy;
17 } else {
18 father[yy] = xx;
19 }
20 }
21 vector<int> father;
22 };
23 class Solution {
24 public:
25 int findCircleNum(vector<vector<int>>& M) {
26 const int n = M.size();
27 UF uf(n);
28 for (int i = 0; i < n; ++i) {
29 for (int j = 0; j < n; ++j) {
30 if (M[i][j] == 1) {
31 uf.connect(i, j);
32 }
33 }
34 }
35 int ret = 0;
36 for (int i = 0; i < uf.father.size(); ++i) {
37 if (i == uf.father[i]) {
38 ret++;
39 }
40 }
41 return ret;
42 }
43 };
View Code
【684】Redundant Connection （2018年11月22日，contest 51 模拟赛做到了）
在本题中，树是一个无环的无向图。输入一个N个结点（编号是1～N）的图，有一条边是多余的，把这条边找出来。
Example 1:
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
/ \
- 3
Example 2:
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The given undirected graph will be like this:
- 1 - 2
| |
- 3
Note:
The size of the input 2D-array will be between 3 and 1000.
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.
题解：我是用并查集解的。对于每一条边的两个结点，如果他们的爸爸不是同一个爸爸，那么就 unoin 这两个结点，如果他们两个的爸爸是同一个爸爸，就说明这条边多余了，直接返回这条边就行了。
1 class Solution {
2 public:
3 int findfather(int x) {
4 return x == father[x] ? x : findfather(father[x]);
5 }
6 void unionNode(int x, int y) {
7 x = findfather(x);
8 y = findfather(y);
9 if (x == y) { return; }
10 father[y] = x;
11 }
12
13 vector<int> findRedundantConnection(vector<vector<int>>& edges) {
14 n = edges.size();
15 father.resize(n+1); //redundant 0
16 for (int i = 0; i < n+1; ++i) {
17 father[i] = i;
18 }
19 vector<int> ret;
20 for (auto e : edges) {
21 int u = min(e[0], e[1]), v = max(e[0], e[1]);
22 if (findfather(v) == findfather(u)) {
23 ret = e;
24 break;
25 } else {
26 unionNode(u, v);
27 }
28 }
29 return ret;
30 }
31 int n = 0;
32 vector<int> father;
33
34 };
View Code
【685】Redundant Connection II (2019年2月2日，UF专题)（Hard）
给了 1～N，N个结点，N条边的有向图，删除一条边之后能形成一棵树，返回需要删除的那条边，如果有多个candidate，返回数组中最后那条需要删除的边。
题解：本题和上一题的不同之处在于，上一个题只是检测是否有环，这个题多了一些业务逻辑的判断，主要是一个树的一个结点不可能有两个爸爸。如有它有两个爸爸，那么这两条边的其中之一一定是答案。那么我们先找出来看看是否存在这种情况（一个结点有两个爸爸），parent[i] 代表 i 结点的爸爸。如果不存在这种情况，直接检测是否有环就好了。如果存在这种情况的话，我们先删除这个结点和它第二个爸爸这条边，看剩下的边是否有环，如果有环的话，就应该返回这个结点和它第一个爸爸这条边。
1 class UF {
2 public:
3 UF(int size) {
4 father.resize(size);
5 for (int i = 0; i < size; ++i) {
6 father[i] = i;
7 }
8 }
9 int find(int x) {
10 return x == father[x] ? x : father[x] = find(father[x]);
11 }
12 void connect(int x, int y) {
13 int xx = find(x), yy = find(y);
14 if (xx == yy) { return; }
15 if (yy < xx) {
16 father[xx] = yy;
17 } else {
18 father[yy] = xx;
19 }
20 }
21 vector<int> father;
22 };
23 class Solution {
24 public:
25 vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
26 const int n = edges.size();
27 UF uf(n+1);
28 vector<int> parent(n+1, 0);
29 vector<int> ans1, ans2;
30 for (auto& e : edges) {
31 int p = e[0], s = e[1];
32 if (parent[s] != 0) {
33 ans1 = {parent[s], s};
34 ans2 = e;
35 e[0] = e[1] = -1; //先把第二条边删除，然后下面用uf检测是否有环
36 break;
37 } else {
38 parent[s] = p;
39 }
40 }
41 for (auto e : edges) {
42 if (e[0] < 0 && e[1] < 0) { continue; }
43 int u = uf.find(e[0]), v = uf.find(e[1]);
44 if (u == v) { //如果说在删除第二条边的情况下，有环，如果有第一条边，就返回第一条边，不然返回第二条边
45 if (!ans1.empty()) {return ans1;}
46 return e;
47 }
48 uf.connect(e[0], e[1]);
49 }
50 return ans2;
51 }
52 };
View Code
【721】Accounts Merge
【737】Sentence Similarity II
【765】Couples Holding Hands
【778】Swim in Rising Water
【803】Bricks Falling When Hit
【839】Similar String Groups
【928】Minimize Malware Spread II