Leetcode并查集

128. 最长连续序列

class Solution {
    int[] father;
    int[] size;
    int res = 1;

    void init() {
        for (int i = 0; i < father.length; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    int findFather(int x) {
        int temp = x;//先保存一下原先的x
        while (x != father[x]) {
            x = father[x];
        }
        //此时x存放的是根结点，下面把路径上所有结点的father改为根结点
        while (temp != father[temp]) {
            int z = temp;
            temp = father[temp];
            father[z] = x;
        }
        return x;
    }

    //合并
    void merge(int a, int b) {
        int faA = findFather(a);
        int faB = findFather(b);
        if (faA != faB) {
            father[faA] = faB;
            size[faB] = size[faA] + size[faB];
            res = Math.max(res, size[faB]);
        }
    }

    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        father = new int[nums.length];
        size = new int[nums.length];
        init();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (Integer key : map.keySet()) {
            if (map.containsKey(key + 1)) {
                merge(map.get(key), map.get(key + 1));
            }
        }
        return res;
    }
}

547. 省份数量

class Solution {
    int[] father;

    private void init() {
        for (int i = 0; i < father.length; i++) {
            father[i] = i;
        }
    }

    private int findFather(int x) {
        while (father[x] != x) {
            x = father[x];
        }
        return x;
    }

    private void union(int a, int b) {
        int faA = findFather(a);
        int faB = findFather(b);
        if (faA != faB) {
            father[faA] = faB;
        }
    }

    public int findCircleNum(int[][] isConnected) {
        this.father = new int[isConnected.length];
        init();
        for (int i = 0; i < isConnected.length; i++) {
            for (int j = i + 1; j < isConnected[0].length; j++) {
                if (isConnected[i][j] == 1) {
                    union(i, j);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < isConnected.length; i++) {
            if (findFather(i) == i) {
                res++;
            }
        }
        return res;
    }
}