LeetCode 547. Friend Circles 朋友圈

题目

https://leetcode.com/problems/friend-circles/description/

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:

Example 2:

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.

讲解

用来判断元素在不在同一个集合、合并集合的并查集 Union Find 对于这套题来说是再合适不过了。

当满足 (M[i][j] == 1 && i != j)条件时候,我们通过并查集的union()把两个朋友圈合并。

视频教学

Java参考代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注