Self improvement is procrastination, and self destruction.
547. Friend Circles
https://leetcode.com/problems/friend-circles/description/
思路: Graph DFS
原始方法:
class Solution547(object):
def findCircleNum(self, M):
"""
:type M: List[List[int]]
:rtype: int
"""
Circles = [];
persons=set(range(0,len(M)))
while persons:
idx_start = list(persons)[0]
circle = set()
circle= self.dfs(M,idx_start,circle)
Circles.append(list(circle))
persons = persons.difference(circle)
TotalCircles = len(Circles)
return TotalCircles
def dfs(self,M,i,circle):
circle.add(i)
idx_friends=self.findNewFriends(M[i],1,circle)
for idx in idx_friends:
circle =self.dfs(M,idx,circle)
return circle
def findNewFriends(self,array,target,Visited):
#returns indices where the array elements are equal to target val
idx_find = [];
for idx,val in enumerate(array):
if val == target and idx not in Visited:
idx_find.append(idx);
return idx_find
改进思路：原题不需要输出到底有哪些朋友圈路径，所以不必存储circle这个信息。直接在遍历的时候更改图M矩阵的值，运算速度会更快。
