【启发】leetcode -- 547. Friend Circles【并查集 + 集合标识更新的时机】

本文主要是介绍【启发】leetcode -- 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 ith and jth 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 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. M[i][i] = 1 for all students.
3. If M[i][j] = 1, then M[j][i] = 1.

题意概述

给定一个矩阵N*N ,表示N个人之间的朋友关系。朋友关系具有传递性，试找出这N个人中有多少个朋友团体。

分析及解答

   public int findCircleNum(int[][] M) {int m = M.length, cnt = 0;int[] root = new int[m]; for (int i = 0; i < m; i++) root[i] = i; for (int i = 0; i < m; i++) for (int j = i + 1; j < m; j++)if (M[i][j] == 1) unionFind(root, i, j);for (int i = 0; i < m; i++)if (i == root[i]) cnt++;return cnt;}void unionFind (int[] root, int v1, int v2) {while (root[v1] != v1) v1 = root[v1]; //find v1's rootwhile (root[v2] != v2) v2 = root[v2]; //find v2's rootif (root[v1] != root[v2]) root[v2] = v1; //unite the 2 subtrees }

class Solution {public static int findCircleNum(int[][] M) {if(M == null || M.length == 0){return 0;}int[] friends =  new int[M.length];for(int i = 0; i < friends.length;i++){friends[i] = -1; // -1 表示尚未分配集合。}for(int i = 0; i < M.length; i++){for(int j = i ; j < M.length;j++){//【关键】初始化 朋友关系。（注意遍历次序：自上而下，自左向右）（一个集合中最小的数作为集合的标志）//只有发现存在朋友关系时，才进行相应的处理。if(M[i][j] == 1){//若之前并未分配集合，首次分配集合。if(friends[j] == -1){friends[j] = i;}else{//若j之前已经分配了集合。则需要进一步传递这种朋友关系。int newRoot = find(friends, j);//因为i中可能有自己的集合标志。而与 j的朋友关系，将这两个集合关联了起来，形成一个集合。所以，//我们将其中一个集合的根标记为另一个集合的根。friends[friends[i]] = newRoot;//将i的根标记为新的集合的根。friends[i] = newRoot;}}}}int result = 0;for(int i = 0; i < friends.length; i++){//每个 i = friends[i]的人，都代表着一个朋友团体。if(i == friends[i]){result ++;}}return result;}public static int find(int[] friends,int i){//查找 i 所属于的集合的根（集合的标志）。while(i != friends[i]){i = friends[i];}return i;}
}

这篇关于【启发】leetcode -- 547. Friend Circles【并查集 + 集合标识更新的时机】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！