Java Union Find


  • 0
    F

    The find operation of this implementation has worst run time O(n). We could improve the runtime by keep track of the size or using compressed path.

    public class Solution {
        public int findCircleNum(int[][] M) {
            int len = M.length;
            if (len == 0) {
                return 0;
            }
            int[] ids = new int[len];
            int count = len;
            for (int i = 0; i < len; ++i) {
                ids[i] = i;
            }
            for (int i = 0; i < len; ++i) {
                for (int j = 0; j < len; ++j) {
                    if (M[i][j] == 1) {
                        int id1 = find(ids, i);
                        int id2 = find(ids, j);
                        if (id1 != id2) {
                            count--;
                            ids[id1] = id2;
                        }
                    }
                }
            }
            return count;
        }
        private int find(int[] ids, int id) {
            while (ids[id] != id) {
                id = ids[id];
            }
            return id;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.