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.

Difficulty: interview

Starter code:

class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        

Solutions:
class Solution:
     def findCircleNum(self, M):
         N = len(M)
         students = set()
         for i in range(N):
             students.add(i)
         
         num_grp = 0
         while students:
             num_grp += 1
             stack = [students.pop()]
             while stack and students:
                 student = stack.pop()
                 for i in range(N):
                     if M[student][i] == 1 and i in students:
                         stack.append(i)
                         students.discard(i)
         return num_grp


class Solution:
     
     def dfs(self, M, cur):
         for i in range(len(M)):
             if flag[i]:
                 continue
             if M[cur][i]:
                 flag[i] = True
                 self.dfs(M, i)
         
     def findCircleNum(self, M):
         """
         :type M: List[List[int]]
         :rtype: int
         """
         
         nonlocal flag
         flag = [False] * len(M)
         circle = 0
         
         for i in range(len(M)):
             if flag[i]:
                 continue
             flag[i] = True
             circle += 1
             self.dfs(M, i)
         return circle

class Solution:
     def findCircleNum(self, M):
         """
         :type M: List[List[int]]
         :rtype: int
         """
         
         ans=0
         visited=[False for i in range(len(M))]
         def dfs(M,i,visited):
             visited[i]=True
             for j in range(len(M)):
                 if M[i][j]==1 and visited[j]==False:
                     dfs(M,j,visited)
             
             
             
             
         for i in range(len(M)):
             if  not visited[i]:
                 dfs(M,i,visited)
                 ans+=1
         return ans


class Solution:
     def findCircleNum(self, M):
         size = len(M)
         parents = list(range(size))
         #print(parents)
         res = size
         for i in range(size):
             for j in range(i+1,size):
                 rooti = self.findRoot(parents,i)
                 rootj = self.findRoot(parents,j)
                 if rooti != rootj and M[i][j] == 1:
                     parents[rootj] = rooti
                     res -= 1
         return res
                 
     def findRoot(self,parents, i):
         return i if parents[i] == i else self.findRoot(parents,parents[i])

class Solution:
     def findCircleNum(self, M):
         """
         :type M: List[List[int]]
         :rtype: int
         """
         N = len(M)
         seen = set()
         
         def dfs(i):
             for j, flag in enumerate(M[i]):
                 if flag and j not in seen:
                     seen.add(j)
                     dfs(j)
                     
         ans = 0
         for i in range(N):
             if i not in seen:
                 dfs(i)
                 ans += 1
         return ans

class Solution:
     def findCircleNum(self, M):
         """
         :type M: List[List[int]]
         :rtype: int
         """
         
         n = len(M)
         seen = set()
         groups = 0
         
         for idx in range(n):
             if idx not in seen:
                 #print(idx)
                 groups += 1
                 seen.add(idx)
                 front = {idx}
                 while len( front ) > 0:
                     #print(front, seen)
                     newFront = set()
                     for cIdx in front:
                         for fIdx in range(n):
                             if M[cIdx][fIdx] == 1 and fIdx not in seen:
                                 seen.add(fIdx)
                                 newFront.add(fIdx)
                     front = newFront
         return groups
         
         
         


class Solution:
     def findCircleNum(self, M):
         """
         :type M: List[List[int]]
         :rtype: int
         """
         n = len(M)
         table = [i for i in range(n)]
         def find(x):
             tmp = x
             while table[tmp] != tmp:
                 tmp = table[tmp]
             table[x] = tmp
             return tmp
             
         
         def union(x, y):
             table[find(x)] = find(y)
         
         for i in range(n):
             for j in range(i+1, n):
                 if M[i][j] == 1:
                     union(i, j)
         print(table)
         return len(set(find(x) for x in range(n)))
                 
         
         
         


class UnionFind(object):
     def __init__(self, n):
         self.parent = dict()
         self.circles = n
         for i in range(n):
             self.parent[i] = i
             
     def find(self, s):
         while self.parent[s] != s:
             self.parent[s] = self.parent[self.parent[s]]
             s = self.parent[s]
         return s
     
     def union(self, s1, s2):
         root_s1 = self.find(s1)
         root_s2 = self.find(s2)
         if root_s1 != root_s2:
             self.parent[root_s2] = root_s1
             self.circles -= 1
         
         
 
 class Solution:
     
     def findCircleNum(self, M):
         """
         :type M: List[List[int]]
         :rtype: int
         """
         if M is None or len(M) == 0:
             return 0
         
         n = len(M)
         uf = UnionFind(n)
         
         for i in range(n):
             for j in range(i + 1, n):
                 if M[i][j] == 1:
                     uf.union(i, j)
                     
         return uf.circles
         

class Solution(object):
 	def findCircleNum(self, M):
 		seen = set()
 
 		def dfs(n):
 			if n in seen:
 				return
 			# print('walk', n)
 			seen.add(n)
 			neighbors = [i for i,val in enumerate(M[n]) if val == 1]
 
 			for neighbor in neighbors:
 				dfs(neighbor)
 
 		count = 0
 		for j, row in enumerate(M):
 			for i, item in enumerate(row):
 				if j in seen or i in seen:
 					continue
 
 				count += 1
 				# print('start',j,i)
 				dfs(i)
 
 		return count

class Solution:
     def findCircleNum(self, M):
         """
         :type M: List[List[int]]
         :rtype: int
         """
     # dfs solution
     #     seen = set()
     #     rtn = 0
     #     for i in range(len(M)):
     #         if i not in seen:
     #             rtn += 1
     #             self.dfs(i, M, seen)
     #     return rtn
     # def dfs(self,i,M,seen):
     #     for nei,adj in enumerate(M[i]):
     #         if adj and nei not in seen:
     #             seen.add(nei)
     #             self.dfs(nei, M, seen)
     
         # union find solution
         ds = DisjointSet()
         for i in range(len(M)):
             ds.make_set(i)
         for i in range(len(M)):
             for j in range(i,len(M)):
                 if M[i][j]==1:
                     ds.union(i,j)
         return ds.num_sets
 
 class Node:
     def __init__(self,data):
         self.data=data
         self.parent=self
         self.rank=0
 class DisjointSet:
     def __init__(self):
         self.map={}
         self.num_sets=0
     def make_set(self,i):
         node = Node(i)
         self.map[i]=node
         self.num_sets+=1
     def union(self,i,j):
         node1 = self.map[i]
         node2 = self.map[j]
         parent1 = self.find_set(node1)
         parent2 = self.find_set(node2)
         if parent1 == parent2:
             return
         if parent1.rank >= parent2.rank:
             if parent1.rank==parent2.rank:
                 parent1.rank+=1
             parent2.parent=parent1
         else:
             parent1.parent = parent2
         self.num_sets-=1
     def find_set(self,node):
         if node.parent==node:
             return node
         node.parent = self.find_set(node.parent)
         return node.parent
         

class Solution:
 
     def find(self, u):
         if self.parent[u] == u:
             return u
         else:
             root_u = self.find(self.parent[u])
             self.parent[u] = root_u
             return self.find(self.parent[u])
 
     def union(self, u, v):
         parent_u = self.find(u)
         parent_v = self.find(v)
         self.parent[parent_u] = parent_v
 
     def findCircleNum(self, M):
         if len(M) == 0:
             return 0
         n = len(M)
         self.parent = [i for i in range(n)]
 
         for i in range(n):
             for j in range(i+1, n):
                 if M[i][j] == 1:
                     self.union(i, j)
         friend_set = set()
         for i in range(n):
             friend_set.add(self.find(i))
 
         print(self.parent)
         return len(friend_set)

class UnionFind(object):
     def __init__(self, n):
         self.__parent = dict()
         self.__circles = n
         for i in range(n):
             self.__parent[i] = i
         
     @property
     def parent(self):
         return self.__parent
     
     @parent.setter
     def parent(self, key, value):
         self.__parent[key] = val
     
     @property
     def circles(self):
         return self.__circles
     
     def circles_decrement(self):
         self.__circles -= 1
         
         
     def find(self, s):
         while self.parent[s] != s:
             self.parent[s] = self.parent[self.parent[s]]
             s = self.parent[s]
         return s
     
     def union(self, s1, s2):
         root_s1 = self.find(s1)
         root_s2 = self.find(s2)
         if root_s1 != root_s2:
             self.parent[root_s2] = root_s1
             self.circles_decrement()
         
 
 class Solution:
     def findCircleNum(self, M):
         """
         :type M: List[List[int]]
         :rtype: int
         """
         if M is None or len(M) == 0:
             return 0
         
         n = len(M)
         uf = UnionFind(n)
         
         for i in range(n):
             for j in range(i + 1, n):
                 if M[i][j] == 1:
                     uf.union(i, j)
                     
         return uf.circles
         

class Solution:
     def findCircleNum(self, M):
         """
         :type M: List[List[int]]
         :rtype: int
         """
         if M == None:
             return 0
         
         n = len(M)
         map1 = [[] for x in range(n)]
         
         #build graph
         for i in range(n):
             for j in range(n):
                 if i != j and M[i][j] == 1:
                     if j not in map1[i]:
                         map1[i].append(j)
                     if i not in map1[j]:
                         map1[j].append(i)
                         
         #bfs
         queue = collections.deque()
         hash1 = set()
         
         count = 0
         for i in range(n):
             if i not in hash1:
                 count += 1
                 queue.append(i)
                 hash1.add(i)
                 
                 while queue:
                     node = queue.popleft()
                     
                     for neighbor in map1[node]:
                         if neighbor in hash1:
                             continue
                         else:
                             queue.append(neighbor)
                             hash1.add(neighbor)
             queue.clear()
             
         return count