547. Friend Circles

Version #1 Union Find
[3RD TRY]
56.87 %
class Solution {
    private int count;
private int[] id;
private int[] size;
public int findCircleNum(int[][] M) {
int len = M.length;
count = len; // each person is connected to himself by default
id = new int[len];
size = new int[len];
for (int i = 0; i < len; i++) {
id[i] = i;
size[i] = 1;
}
for (int i = 0; i < len; i++) {
for (int j = 0; j < i; j++) { // not need to check j==i, since a id[i] = i already
if (M[i][j] == 1) union(i, j);
}
}
return count;
}
private int root(int i) {
while (id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}
private void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) return;
count--; // two disjoint parts are union together
if (size[rootP] < size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
}
}


[2ND TRY]
74.85 %
class Solution {
    class UF {
private int[] id;
private int[] size;
private int count;
public UF(int N) {
id = new int[N];
size = new int[N];
count = N;
for (int i = 0; i < N; i++) {
id[i] = i;
size[i] = 1;
}
}

private int root(int i) {
while (id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}

public void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) {
return;
}
count--;
if (size[rootP] < size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
}
public int getCount() {
return count;
}
}

public int findCircleNum(int[][] M) {
if (M == null || M.length == 0 || M[0] == null || M[0].length == 0) {
return 0;
}
int len = M.length;
UF uf = new UF(len);
for (int i = 0; i < len; i++) {
for (int j = 0; j < i; j++) {
if (M[i][j] == 1) {
uf.union(i, j);
}
}
}
return uf.getCount();
}
}


[1ST TRY]
63.74%
public class Solution {
    private int[] father;
    private int count;
    public int findCircleNum(int[][] M) {
        if (M == null || M.length == 0 || M[0] == null || M[0].length == 0) return 0;
        int length = M.length;
        father = new int[length];
        for (int i = 0; i < length; i++) father[i] = i;
        //Each student is a distinct friend circle
        count = length;
        //Merge two students if they are friends
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (M[i][j] == 1) union(i, j);
            }
        }
        return count;
    }
    //find the root of the current student and do path compression
    private int find(int x) {
        if (father[x] == x) return x;
        father[x] = find(father[x]);
        return father[x];
    }
    //merge two sets together if they have different roots
    private void union(int a, int b) {
        int rootA = find(a);
        int rootB= find(b);
        if (rootA != rootB) {
            father[rootA] = rootB;
            count--;
        }
    }
}