# 547. Friend Circles

## 题目要求

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 N*N matrix M representing the friend relationship between students in the class. If `M[i][j]` = 1, then the ithand jthstudents 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 0th and 1st students are direct friends, so they are in a friend circle. The 2nd 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 0th and 1st students are direct friends, the 1st and 2nd students are direct friends, so the 0th and 2nd 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. Mi = 1 for all students.
3. If Mi = 1, then Mj = 1.

## 思路一：深度优先遍历

```public int findCircleNum(int[][] M) {
int numOfFriends = M.length;
int count = 0;
for (int i = 0 ; i<numOfFriends ; i++) {
if (M[i][i] == 1) {
count++;
traverseFriendCircle(M, i, i);
}
}
return count;
}

public void traverseFriendCircle(int[][] M, int friendIndex, int fromFriendIndex) {
M[fromFriendIndex][friendIndex] = 0;
M[friendIndex][fromFriendIndex] = 0;
M[friendIndex][friendIndex] = 0;
for (int i = 0 ; i<M.length ; i++) {
if (M[friendIndex][i] == 1) {
traverseFriendCircle(M, i, friendIndex);
}
}
}```

## 思路二：Union Find

```private int[] parentRoot;
private int[] ranks;

private int findParent(int i) {
while (i != parentRoot[i]) {
parentRoot[i] = parentRoot[parentRoot[i]];
i = parentRoot[i];
}
return i;
}

private void union(int i, int j) {
int parentOfI = findParent(i);
int parentOfJ = findParent(j);
if (parentOfI == parentOfJ) {return;}
if (ranks[parentOfI] > ranks[parentOfJ]) {
parentRoot[parentOfJ] = parentOfI;
ranks[parentOfI]++;
} else {
parentRoot[parentOfI] = parentOfJ;
ranks[parentOfJ]++;
}
}

public int findCircleNum2(int[][] M) {
int numOfFriends = M.length;
parentRoot = new int[numOfFriends];
ranks = new int[numOfFriends];
for (int i = 0 ; i < numOfFriends ; i++) {
parentRoot[i] = i;
}
for (int i = 0 ; i<numOfFriends ; i++) {
for (int j = i+1 ; j<numOfFriends ; j++){
if (M[i][j] == 1) {
union(i, j);
}
}
}
int count = 0;
for (int i = 0 ; i<numOfFriends ; i++) {
if (parentRoot[i] == i) {
count++;
}
}
return count;
}```

0 条评论

• ### leetcode363. Max Sum of Rectangle No Larger Than K

现有一个由整数构成的矩阵，问从中找到一个子矩阵，要求该子矩阵中各个元素的和为不超过k的最大值，问子矩阵中元素的和为多少? 注：后面的文章中将使用[左上角顶点坐标...

• ### 395. Longest Substring with At Least K Repeating Characters

这是一个经典的分治法解决的问题，关键在于我们如何将这个问题分解为更小的子问题。反过来想，这个子字符串一定不包含什么元素呢？当一个元素出现的总次数小于k，那么该元...

• ### leetcode540. Single Element in a Sorted Array

You are given a sorted array consisting of only integers where every element app...

• ### 【POJ 2886】Who Gets the Most Candies?

约瑟夫问题的升级版，每次出去的是前一个出去的人位置+手上的数字（正往前，负往后）。第i个出去的人拿的糖是i的约数的个数。求拿糖最多的人和他的糖果数。

• ### C# Tryparse的用法

int.TryParse(n1.Text, out P_int_Number) 其中第一个参数代表被转换的参数，第二个参数为转换后的参数 int类型，成功返回T...

• ### 杭电1003--动态规划

思路：用数组a[]记录序列中的数，对于a[i]只有两种可能 1.为一个序列的首2.为一个序列的尾。 用数组b[i]记录以第i个数结尾的序列的最大和，则 b[...

• ### 用归并排序求逆序对数（包括归并排序算法实现及代码）

那么我们很容易想到这个题有一种O（n*n）的暴力解法，但这不是我们所需要的，所以，要想归并排序来实现求逆序对数，那么首先我们要了解并掌握归并排序算法。

• ### 最大连续子序列和（最大子数组和）四种最详细的解法

解法1：穷举暴力法 枚举左端点跟右端点，然后遍历更新所有的子序列和，最终得到结果就是最大的

• ### 不引入新的数组，实现数组元素交换位置函数

最近遇到一道C++的面试题，要求不引入新的数组，实现数组元素交换位置函数，看似挺简单的，却还是花费了我不少时间，这里记录下来，给大家一个简单的...