Java 10ms Union Find, short and easy


  • 0
    K

    class Solution {
    int[] fa;
    public int findCircleNum(int[][] M) {
    int n = M.length, res = 0;
    fa = new int[n];
    for(int i = 0; i<n; i++) fa[i] = i;
    for(int i = 0; i<n; i++)
    for(int j = 0; j<i; j++) if(M[i][j] == 1) fa[find(j)] = find(i);
    for(int i = 0; i<n; i++) if(find(i)==i) res++;
    return res;
    }
    public int find(int i){
    while(fa[fa[i]]!=fa[i]) fa[i] = find(fa[i]);
    return fa[i];
    }
    }


Log in to reply
 

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