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.

思路一:深度优先遍历

每当遇到一个还没有加入任何朋友圈的人(即Mi=1),就开始遍历其还未加入任何朋友圈的朋友,并再访问这些朋友的朋友,将其加入改人所在的朋友圈(使Mj=0, Mi=0),直到M中所有的值都为0,说明找到了所有的朋友圈。

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

这题就是标准的Union Find的题目,通过找到所有有关联的节点,将其加入到一个关联树中,利用标准的Union Find的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...

    zls365
  • 杭电1003--动态规划

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

    用户7727433
  • 洛谷P3722 [AH2017/HNOI2017]影魔(线段树 set spaly)

    attack
  • 用归并排序求逆序对数(包括归并排序算法实现及代码)

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

    用户7727433
  • 最大连续子序列和(最大子数组和)四种最详细的解法

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

    用户7727433
  • 不引入新的数组,实现数组元素交换位置函数

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

    用户1221057

扫码关注云+社区

领取腾讯云代金券