Union Find 模板

Union Find

Union Find 动态的计算联通块问题

结构

• global variables

• constructor()

• find(int x)

• union(int a, int b)

模板 (Map)

• global variables

  private Map<Integer, Integer> f;

• constructor()

  UnionFind(int n) {
    this.f = new HashMap<Integer, Integer>();
    for (int i = 0; i < n; i++) {
        f.put(i, i);
    }
  }

• find(int x)

  int find(int x) {
    int root = x;
    // 找到“根”
    while (f.get(root) != root) {
        root = f.get(root);
    }
    // 拆“整”为“零”，把每个元素直接接到“根”上
    while (root != x) {
        int nx = f.get(x);
        f.put(x, root);
        x = nx;
    }
    return root;
  }

• union(int a, int b)

  void union(int a, int b) {
    int rA = find(a);
    int rB = find(b);
    if (rA != rB) {
        f.put(rB, rA);
    }
  }

例题

1. Friend Circles

   根据模板添加额外的全局变量，比如此题需要count，在每次合并的时候count--，在初始化的时候或者写一个setter和getter去给count赋值和取值

   public class Solution {
    class UnionFind {
        private int count;
        private Map<Integer, Integer> f;
        UnionFind(int n) {
            this.count = 0;
            this.f = new HashMap<Integer, Integer>();
            for (int i = 0; i < n; i++) {
                f.put(i, i);
            }
        }
        void union(int a, int b) {
            int rA = find(a);
            int rB = find(b);
            if (rA != rB) {
                f.put(rB, rA);
                this.count--;
            }
        }
        int find(int x) {
            int root = x;
            while (f.get(root) != root) {
                root = f.get(root);
            }
            while (root != x) {
                int nx = f.get(x);
                f.put(x, root);
                x = nx;
            }
            return root;
        }
        void setCount(int count) {
            this.count = count;
        }
        int getCount() {
            return this.count;
        }
    }
    public int findCircleNum(int[][] M) {
        int n = M.length;
        UnionFind unionFind = new UnionFind(n);
        unionFind.setCount(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (M[i][j] == 1) {
                    unionFind.union(i, j);
                }
            }
        }
        return unionFind.getCount();
    }
   }

2. Number of Islands II

   同上一题，但是区别是此题为动态计算每一次的岛屿数，所以union find最合适， 注意把二维数组值变为一维的话，用x * m + y，这是把二维数组拉直，找到其index

   public class Solution {
    class UnionFind {
        private int count;
        private Map<Integer, Integer> f;
        UnionFind(int n) {
            this.count = 0;
            this.f = new HashMap<Integer, Integer>();
            for (int i = 0; i < n; i++) {
                f.put(i, i);
            }
        }
        int find(int x){
            int root = x;
            while (f.get(root) != root) {
                root = f.get(root);
            }
            while (x != root) {
                int nx = f.get(x);
                f.put(x, root);
                x = nx;
            }
            return root;
        }
        void union(int a, int b) {
            int rootA = find(a);
            int rootB = find(b);
            if (rootA != rootB) {
                this.f.put(rootB, rootA);
                this.count--;
            }
        }
        int getCount() {
            return this.count;
        }
        void setCount(int count) {
            this.count = count;
        }
    }
    public List<Integer> numIslands2(int n, int m, Point[] operators) {
        // write your code here
        List<Integer> result = new ArrayList<>();
        if (operators == null || operators.length == 0) {
            return result;
        }
        int[] deltaX = new int[]{-1, 0, 1, 0};
        int[] deltaY = new int[]{0, 1, 0, -1};
        int count = 0;
        int[][] island = new int[n][m];
        UnionFind unionFind = new UnionFind(n * m);
        for (Point operator : operators) {
            if (island[operator.x][operator.y] == 1) {
                result.add(count);
                continue;
            }
            island[operator.x][operator.y] = 1;
            count++;
            unionFind.setCount(count);
            for (int i = 0; i < 4; i++) {
                int nx = operator.x + deltaX[i];
                int ny = operator.y + deltaY[i];
                if (nx >= 0 && nx < n &&
                    ny >= 0 && ny < m &&
                    island[nx][ny] == 1) {
                    unionFind.union(mapReduce(operator.x, operator.y, m), mapReduce(nx, ny, m));
                }
            }
            count = unionFind.getCount();
            result.add(count);
        }
        return result;
    }
    private int mapReduce(int x, int y, int m) {
        return x * m + y;
    }
   }