547. Friend Circles

Description

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a NN* matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the i_th and j_th students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

Example 1:

Input:
[[1,1,0],
[1,1,0],
[0,0,1]]
Output: 2
Explanation:The 0_th and 1_st students are direct friends, so they are in a friend circle.
The 2_nd student himself is in a friend circle. So return 2.

Example 2:

Input:
[[1,1,0],
[1,1,1],
[0,1,1]]
Output: 1
Explanation:The 0_th and 1_st students are direct friends, the 1_st and 2_nd students are direct friends,
so the 0_th and 2_nd students are indirect friends. All of them are in the same friend circle, so return 1.

Note:

1. N is in range [1,200].
2. M[i][i] = 1 for all students.
3. If M[i][j] = 1, then M[j][i] = 1.

Solution

Union-Find, time O(n ^ 2), space O(n)

其实就是求连通区的个数。注意连通区初始化为n，而非n ^ 2哦！

class Solution {
    public int findCircleNum(int[][] M) {
        int n = M.length;
        int[] parent = new int[n];
        for (int i = 0; i < parent.length; ++i) {
            parent[i] = i;
        }
        
        int circles = n;    // important
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (M[i][j] != 1) {
                    continue;
                }
                
                int iset = find(parent, i);
                int jset = find(parent, j);
                if (iset != jset) {
                    union(parent, iset, jset);
                    --circles;
                }
            }
        }
        
        return circles;
    }
    
    public int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }
    
    public void union(int[] parent, int xset, int yset) {
        parent[xset] = yset;
    }
}