Solution to LeetCode 547 Friend Circles
LeetCode 547
Friend Circles (Median). [link]
1] DFS. Given a node, find the maximal connected components and mark all nodes in it as visited. Time complexity O(n^2). Space complexity O(n).
class Solution(object):
def findCircleNum(self, isConnected):
"""
:type isConnected: List[List[int]]
:rtype: int
"""
def DFS(C, cur, n):
for i in range(n):
if C[cur][i] == 1: # is friend
C[cur][i] = C[i][cur] = 0 # remove all friends in current friend group
DFS(C, i, n)
n = len(isConnected)
count = 0
for i in range(n):
if isConnected[i][i] == 1: # is friend
count += 1
DFS(isConnected, i, n)
return count
2] Union-Find- Set.
class UnionFind:
def __init__(self):
self.father = {}
# count the number of sets
self.num_of_sets = 0
def find(self,x):
root = x
while self.father[root] != None:
root = self.father[root]
while x != root:
original_father = self.father[x]
self.father[x] = root
x = original_father
return root
def merge(self,x,y):
root_x,root_y = self.find(x),self.find(y)
if root_x != root_y:
self.father[root_x] = root_y
self.num_of_sets -= 1
def add(self,x):
if x not in self.father:
self.father[x] = None
self.num_of_sets += 1
class Solution:
def findCircleNum(self, M: List[List[int]]) -> int:
uf = UnionFind()
for i in range(len(M)):
uf.add(i)
for j in range(i):
if M[i][j]:
uf.merge(i,j)
return uf.num_of_sets
Template of Union-Find Set
class UnionFind:
def __init__(self):
self.father = {}
def find(self,x):
root = x
while self.father[root] != None:
root = self.father[root]
# optimization: path compression O(log*n)
while x != root:
original_father = self.father[x]
self.father[x] = root
x = original_father
return root
def merge(self,x,y,val):
root_x,root_y = self.find(x),self.find(y)
if root_x != root_y:
self.father[root_x] = root_y
def is_connected(self,x,y):
return self.find(x) == self.find(y)
def add(self,x):
if x not in self.father:
self.father[x] = None
