首页 > itarticle > union find

union find

admin 11月 13, 2020 0

Common

LC 947. Most Stones Removed with Same Row or Column

On a 2D plane, we place stones at some integer coordinate points. Each coordinate point may have at most one stone.

Now, a move consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

Example 1:

Input: stones = [ [0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
Example 2:

Input: stones = [ [0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
Example 3:

Input: stones = [ [0,0]]
Output: 0

If we connect all stones with same column or row as an island, then this problem wants us to remove stones until there is only one stone left in this union.
So in the result, #of islands = #of left stones.
And the result = #of all stones - #of islands.

=>

This problem can be reversed to count the number of islands.

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
 
class Solution {
     int count = 0;
    Map<String, String> map = new HashMap<>();

    public int removeStones(int[][] stones) {
        count = stones.length;
        for(int i = 0; i < stones.length; i++){
            String stone = stones[i][0] + " " + stones[i][1];
            map.put(stone, stone);
        }
        for(int i = 0; i < stones.length; i++){
            String stone1 = stones[i][0] + " " + stones[i][1];
            for(int j = 0; j < stones.length; j++){
                if(stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                    String stone2 = stones[j][0] + " " + stones[j][1];
                    union(stone1, stone2);
                }
            }
        }
        return stones.length - count;
    }
    public void union(String first, String next){
        String firstR = find(first);
        String nextR = find(next);
        if(!firstR.equals(nextR)) {
            map.put(firstR, nextR);
            count--;
        }

    }

    public String find(String first){
        if(!first.equals(map.get(first))){
            map.put(first, find(map.get(first)));
        }
        return map.get(first);
    }
}
 
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
 
class  {
public:
    int removeStones(vector<vector<int>>& stones) {
        for(int i = 0; i < stones.size(); i++){
            uni(stones[i][0], ~stones[i][1]);
        }
        return stones.size()-island;
    }
    unordered_map<int, int> fmap;
    int island = 0;
    int find(int x){
        if(fmap.find(x) == fmap.end()){
            fmap[x] = x;
            island++;
        }
        if(fmap[x] != x)
            fmap[x] = find(fmap[x]);
        return fmap[x];
    }
    void uni(int x, int y){
        int xroot = find(x);
        int yroot = find(y);
        if(xroot != yroot){
            fmap[xroot] = yroot;
            island--;
        }
    }
};

LC 959. Regions Cut By Slashes

not a typical problem but an interesting one.

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
 
class  {
public:
    vector<int> regions;
    int islands, n;
    int regionsBySlashes(vector<string>& grid) {
        n = grid.size();
        islands = n*n*4;
        for(int i = 0; i < n*n*4; i++){
            regions.push_back(i);
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i > 0)
                    uni(g(i-1, j, 2), g(i, j, 0));
                if(j > 0)
                    uni(g(i, j-1, 1), g(i, j, 3));
                 if(grid[i][j] != '/'){
                    uni(g(i, j, 0), g(i, j, 1));
                    uni(g(i, j, 2), g(i, j, 3));
                }
                if(grid[i][j] != '\'){
                    uni(g(i, j, 0), g(i, j, 3));
                    uni(g(i, j, 2), g(i, j, 1));
                }
            }
        }
        return islands;

    }
    int find(int x){
        if(x != regions[x])
            regions[x] = find(regions[x]);
        return regions[x];
    }
    void uni(int x, int y){
        int xroot = find(x);
        int yroot = find(y);
        if(xroot != yroot){
            regions[xroot] = yroot;
            islands--;
        }
    }
    int g(int i, int j, int k){
        return (i*n + j) * 4 + k;
    }
};

323. Number of Connected Components in an Undirected Graph

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]

0          3
|          |
1 --- 2    4

Output: 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
int find(int x, vector<int> roots){
 if(x != roots[x])
     roots[x] = find(roots[x], roots);
  return roots[x];
}
int countComponents(int n, vector<pair<int, int>>& edges) {
  vector<int> roots(n, 0);
  for(int i = 0; i < n; i++)
      roots[i] = i;
  for(auto p : edges){
      int sroot = find(p.first, roots);
      int eroot = find(p.second, roots);
      if(sroot != eroot){
          roots[sroot] = eroot;
          n--;
      }
  }
  return n;
}

###

index group

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能