班上有?N?名學生。其中有些人是朋友，有些則不是。他們的友誼具有是傳遞性。如果已知 A 是 B?的朋友，B 是 C?的朋友，那么我們可以認為 A 也是 C?的朋友。所謂的朋友圈，是指所有朋友的集合。

給定一個?N * N?的矩陣?M，表示班級中學生之間的朋友關系。如果M[i][j] = 1，表示已知第 i 個和 j 個學生互為朋友關系，否則為不知道。你必須輸出所有學生中的已知的朋友圈總數。

示例 1:

輸入:?
[[1,1,0],
?[1,1,0],
?[0,0,1]]
輸出: 2?
說明：已知學生0和學生1互為朋友，他們在一個朋友圈。
第2個學生自己在一個朋友圈。所以返回2。
示例 2:

輸入:?
[[1,1,0],
?[1,1,1],
?[0,1,1]]
輸出: 1
說明：已知學生0和學生1互為朋友，學生1和學生2互為朋友，所以學生0和學生2也是朋友，所以他們三個在一個朋友圈，返回1。
注意：

N 在[1,200]的范圍內。
對于所有學生，有M[i][i] = 1。
如果有M[i][j] = 1，則有M[j][i] = 1。

思路：并查集差他丫的，最后遍歷一下看看有多少個根就好

public class Solution {int[] parent;//這是記錄關系的數組//查找int find(int parent[], int i) {if (parent[i] == -1)return i;return find(parent, parent[i]);}//合并void union(int parent[], int x, int y) {int xset = find(parent, x);int yset = find(parent, y);if (xset != yset)parent[xset] = yset;}public int findCircleNum(int[][] M) {int len=M.length;parent = new int[len];Arrays.fill(parent, -1);for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {if (M[i][j] == 1)union(parent, i, j);}}int count = 0;//查根的數量for (int i = 0; i < len; i++)if (parent[i] == -1)count++;return count;}
}

?