Clean java union find


  • 0
    L
    public int findCircleNum(int[][] M) {
            if (M == null || M.length == 0 || M.length != M[0].length) {
                return 0;
            }
            int m = M.length;
            int res = m;
            int[] root = new int[m];
            for (int i = 0; i < m; ++i) {
                root[i] = i;
            }
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < m; ++j) {
                    if (i != j && M[i][j] == 1) {
                        int p1 = findRoot(root, i);
                        int p2 = findRoot(root, j);
                        if (p1 != p2) {
                            --res;
                            root[p2] = p1;
                        }
                    }
                }
            }
            return res;
        }
    
        private int findRoot(int[] root, int i) {
            while (root[i] != i) {
                root[i] = root[root[i]];
                i = root[i];
            }
            return i;
        }
    

  • 0
    R

    Good solution! But I think you can change this part

    for (int i = 0; i < m; ++i) {
                for (int j = 0; j < m; ++j) {
                    if (i != j && M[i][j] == 1) {
    

    to

    for (int i = 0; i < m; ++i) {
                for (int j = 0; j < i; ++j) {
                    if (M[i][j] == 1) {
    

    and it can save some time because we just need to check half of matrix.


Log in to reply
 

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