算法——朋友圈（并查集）

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
链接: leetcode.

解题思路：这是一个典型的并查集的问题，将朋友圈中，是朋友的人加入一个并查集。在初始情况下，所有人都不是朋友，则朋友圈的数量就是人的总数，每当检测到两个朋友不在一个并查集，那么就将其加入一个并查集，然后朋友圈的总数减一。

class Solution {
    List<Integer> p = new ArrayList<>();
    public int findCircleNum(int[][] M) {
        int n = M.length;
        int res = n;


        for(int i = 0; i < n; i++){
            p.add(i);
        }

        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(M[i][j] == 1) {
                    if(find(i) != find(j)) {
                        res --;
                        p.set(find(i), find(j));
                    }
                }
            }
        }

        return res;

    }

    public int find(int x) {
        if(x != p.get(x)){
            p.set(x, find(p.get(x)));
        }

        return p.get(x);
    }
}