Leetcode547 朋友圈 图的DFS与unionFind算法

 

　　DFS 解法：

public final int findCircleNum(int[][] M) {
        if (M == null || M.length == 0) return 0;
        int re = 0;
        for (int i = 0; i < M.length; i++) {
            for (int j = 0; j < M[0].length; j++) {
                if (M[i][j] != 1) continue;
                M[i][j] = 0;
                search(M, j, i + 1);
                re++;
            }
        }
        return re;
    }

    private final void search(int[][] M, int x, int begin) {
        for (int i = 0; i < M.length; i++) {
            if (M[i][x] == 1) {
                M[i][x] = 0;
                search(M, i, begin + 1);
            }
        }
    }

　　unionFind 解法：

　　　　 int[] parents;

        private final int find(int point) {
            if (parents[point] == point) return point;
            return find(parents[point]);
        }

        private final void union(int point0, int point1) {
            int parent0 = find(point0);
            int parent1 = find(point1);
            if (parent0 == parent1) return;
            for (int i = 0; i < parents.length; i++) {
                if (parents[i] == parent1) parents[i] = parent0;
            }
        }

        public final int findCircleNum(int[][] M) {
            if (M.length == 0) return 0;
            int re = 0, len = M.length;
            parents = new int[len];
            for (int i = 0; i < len; i++) parents[i] = i;
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) if (M[i][j] == 1) union(i, j);
            }
            for (int i = 0; i < len; i++) {
                if (parents[i] == i) re++;
            }
            return re;
        }

　　union 方法时间复杂度为 O(N)，采用树形结构，优化 union 方法：

int[] parents;

       private final int find(int point) {
            if (parents[point] == point) return point;
            return find(parents[point]);
        }

        private final void union(int point0, int point1) { 
            int parent0 = find(point0);
            int parent1 = find(point1);
            if (parent0 == parent1) return;
            parents[parent1]=parent0;
        }

        public final int findCircleNum(int[][] M) {
            if (M.length == 0) return 0;
            int re = 0, len = M.length;
            parents = new int[len];
            for (int i = 0; i < len; i++) parents[i] = i;
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) if (M[i][j] == 1) union(i, j);
            }
            for (int i = 0; i < len; i++) {
                if (parents[i] == i) re++;
            }
            return re;
        }

　　在构建树的过程中，因为简单的挑选 point0 为根，很容易造成树的深度过深。采用基于重量选取根的方式减少树的深度：

        int[] parents;
        int[] weights;

        private final int find(int point) {
            if (parents[point] == point) return point;
            return find(parents[point]);
        }

        private final void union(int point0, int point1) {
            int parent0 = find(point0);
            int parent1 = find(point1);
            if (parent0 == parent1) return;
            if (weights[parent0] >= weights[parent1]) {
                parents[parent1] = parent0;
                weights[parent0] += weights[parent1];
            } else {
                parents[parent0] = parent1;
                weights[parent1] += weights[parent0];
            }
        }

        public final int findCircleNum(int[][] M) {
            if (M.length == 0) return 0;
            int re = 0, len = M.length;
            parents = new int[len];
            weights = new int[len];
            for (int i = 0; i < len; i++) parents[i] = i;
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) if (M[i][j] == 1) union(i, j);
            }
            for (int i = 0; i < len; i++) {
                if (parents[i] == i) re++;
            }
            return re;
        }

　　基于深度（秩）可以进一步减小树的深度：

        int[] parents;
        int[] heights;

        private final int find(int point) {
            if (parents[point] == point) return point;
            return find(parents[point]);
        }

        private final void union(int point0, int point1) {
            int parent0 = find(point0);
            int parent1 = find(point1);
            if (parent0 == parent1) return;
            if (heights[parent0] > heights[parent1]) parents[parent1] = parent0;
            else if (heights[parent0] < heights[parent1]) parents[parent0] = parent1;
            else {
                parents[parent1] = parent0;
                heights[parent0]++;
            }
        }

        public final int findCircleNum(int[][] M) {
            if (M.length == 0) return 0;
            int re = 0, len = M.length;
            parents = new int[len];
            heights = new int[len];
            for (int i = 0; i < len; i++) parents[i] = i;
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) if (M[i][j] == 1) union(i, j);
            }
            for (int i = 0; i < len; i++) {
                if (parents[i] == i) re++;
            }
            return re;
        }

　　因为构建树只是为了确定以根节点划分的关系集合，下方节点的从属关系并不重要。保证根节点不变的情况下压缩路径，进一步减小树的深度：

        int[] parents;

        private final int find(int point) {
            if (parents[point] == point) return point;
            return parents[point] = find(parents[point]);
        }

        private final void union(int point0, int point1) {
            int parent0 = find(point0);
            int parent1 = find(point1);
            if (parent0 != parent1) parents[parent0] = parent1;
        }


        public final int findCircleNum(int[][] M) {
            if (M.length == 0) return 0;
            int re = 0, len = M.length;
            parents = new int[len];
            for (int i = 0; i < len; i++) parents[i] = i;
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) if (M[i][j] == 1) union(i, j);
            }
            for (int i = 0; i < len; i++) {
                if (parents[i] == i) re++;
            }
            return re;
        }

　　js unionFind算法：

var findCircleNum = function (M) {
    let len = M.length;
    let parents = [];
    for (let i = 0; i < len; i++) parents[i] = i;
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            if (M[i][j] == 1) union(i, j,parents);
        }
    }
    let re = 0;
    for (let i = 0; i < len; i++) {
        if (parents[i] == i) re++;
    }
    return re;
};


var union = function (point0, point1, parents) {
    let root0 = find(point0, parents);
    let root1 = find(point1, parents);
    if (root0 == root1) return;
    parents[root1] = root0;
}

var find = function (point, parents) {
    if (parents[point] == point) return point;
    return parents[point] = find(parents[point], parents);
}