难度: Medium
原题连接
内容描述
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:
N is in range [1,200].
M[i][i] = 1 for all students.
If M[i][j] = 1, then M[j][i] = 1.
思路 1 - 时间复杂度: O(N^3)- 空间复杂度: O(N)******
发现一件事，只要是关于这种circle类的题目，
- 第一印象如果是关于链表的那么就想到快慢指针
- 第二印象如果是关于图的立马想到union-find
思路就没什么好说的，把这道题看成求图中有多少个联通分量就可以了。
时间复杂度是因为两个for loop，并且调用connected方法会调用find方法，find方法最差到O(n)，所以最终是O(N^3)
空间自然就是O(N)
beats 27.28%
class UnionFind(object):
def __init__(self, n): # 初始化uf数组和组数目
self.count = n
self.uf = [i for i in range(n)]
self.size = [1] * n # 每个联通分量的size
def find(self, x): # 判断节点所属于的组
while x != self.uf[x]:
self.uf[x] = self.uf[self.uf[x]]
x = self.uf[x]
return self.uf[x]
def union(self, x, y): # 连接两个节点
x_root = self.find(x)
y_root = self.find(y)
if x_root == y_root:
return
self.uf[x_root] = y_root
self.size[y_root] += self.size[x_root]
self.size[x_root] = 0
self.count -= 1
def connected(self, x, y): # 判断两个节点是否联通
return self.find(x) == self.find(y)
def count(self): # 返回所有组的数目
return self.count
class Solution(object):
def findCircleNum(self, grid):
"""
:type M: List[List[int]]
:rtype: int
"""
s = UnionFind(len(grid))
for i in range(len(grid)):
for j in range(len(grid[i])):
# 如果i等于j说明是自己，没必要判断
# 只有当该位置为1即互为朋友的时候才需要看是否联通
# 不联通才union，联通也union一来浪费时间二来可能会无故减小count
if j != i and grid[i][j] == 1 and not s.connected(j, i):
s.union(j, i)
return s.count思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******
DFS 也可以，beats 86.11%
class Solution:
def findCircleNum(self, M):
"""
:type M: List[List[int]]
:rtype: int
"""
def dfs(i, visited, M):
for j in range(len(M)):
if M[i][j] == 1 and j not in visited:
visited.add(j)
dfs(j, visited, M)
visited = set()
cnt = 0
for i in range(len(M)):
if i not in visited:
dfs(i, visited, M)
cnt += 1
return cnt