# LeetCode 547Friend Circles

## LeetCode 547 Friend Circles Problem

``````class Solution(object):
def findCircleNum(self, M):
"""
:type M: List[List[int]]
:rtype: int
"""
# because
visited =  * len(M)
count = 0
for i in range(len(M)):
if visited[i] == 0:
self.dfs(M, visited, i)
count += 1
return count

def dfs(self, M, visited, i):
for j in range(len(M)):
if M[i][j] == 1 and visited[j] == 0:
visited[j] = 1
self.dfs(M, visited, j)

# def findCircleNum(self, M):
#     # BFS
#     visited =  * len(M)
#     count = 0
#     queue = []
#     for i in range(len(M)):
#         if visited[i] == 0:
#             queue.append(i)
#             while queue:
#                 curr = queue.pop(0)
#                 visited[curr] = 1
#                 for j in range(len(M)):
#                     if M[curr][j] == 1 and visited[j] == 0:
#                         queue.append(j)
#             count += 1
#     return count

#     def findCircleNum(self, M):
#         # Union Find
#         union = Union()
#         for i in range(len(M)):
#         for i in range(len(M)):
#             for j in range(i + 1, len(M)):
#                 if M[i][j] == 1:
#                     union.union(i, j)
#         return union.count

# class Union(object):
#     """
#     weighted quick union find
#     """
#     def __init__(self):
#         # both dic and list is fine
#         self.id = {}
#         self.sz = {}
#         self.count = 0

#     def count(self):
#         return self.count

#     def connected(self, p, q):
#         return self.find(p) == self.find(q)

#         # init
#         self.id[p] = p
#         self.sz[p] = 1
#         self.count += 1

#     def find(self, p):
#         """
#         find root of p, and compress path
#         """
#         while p != self.id[p]:
#             self.id[p] = self.id[self.id[p]]
#             p = self.id[p]
#         return p

#     def union(self, p, q):
#         """
#         connect p and q
#         """
#         i, j = self.find(p), self.find(q)
#         if i == j:
#             return
#         if self.sz[i] > self.sz[j]:
#             i, j = j, i
#         self.id[i] = j
#         self.sz[j] += self.sz[i]
#         self.count -= 1
``````

## List of all Friend Circles problems

Leetcode 547 Friend Circles problem solution in python3 with explanation. This is the best place to expand your knowledge and get prepared for your next interview.

for i in range(len(M)):

for i in range(len(M)):

for j in range(i + 1, len(M)):

if M[i][j] == 1:

union.union(i, j)

return union.count

class Union(object):

"""

weighted quick union find

"""

def __init__(self):

# both dic and list is fine

self.id = {}

self.sz = {}

self.count = 0

def count(self):

return self.count

def connected(self, p, q):

return self.find(p) == self.find(q)

# init

self.id[p] = p

self.sz[p] = 1

self.count += 1

def find(self, p):

"""

find root of p, and compress path

"""

while p != self.id[p]:

self.id[p] = self.id[self.id[p]]

p = self.id[p]

return p

def union(self, p, q):

"""

connect p and q

"""

i, j = self.find(p), self.find(q)

if i == j:

return

if self.sz[i] > self.sz[j]:

i, j = j, i

self.id[i] = j

Feedback is the most important part of any website.