[JAVA] Clean and concise Union Find code


  • 0
    N

    public int findCircleNum(int[][] M) {
    if (M == null || M.length == 0 || M[0].length == 0) {
    return 0;
    }
    int[] father = new int[M.length];
    for (int i = 0; i < M.length; i++) {
    father[i] = i;
    }
    Set<Integer> set = new HashSet<>();
    int fatherI = 0;
    int fatherJ = 0;
    for (int i = 0; i < M.length; i++) {
    for (int j = 0; j < M[0].length; j++) {
    if (M[i][j] == 1) {
    connect(i, j, father);
    }
    }
    }
    for (int i = 0; i < M.length; i++) {
    int temp = find(i, father);
    if (!set.contains(temp)) {
    set.add(temp);
    }
    }
    return set.size();
    }
    private int find(int i, int[] father) {
    if (i == father[i]) {
    return i;
    }
    father[i] = find(father[i], father);
    return father[i];
    }
    private void connect(int i, int j, int[] father) {
    int fatherI = find(i, father);
    int fatherJ = find(j, father);
    father[fatherI] = fatherJ;
    }


Log in to reply
 

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