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.

Source: leetcode | Difficulty: MEDIUM_HARD

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):
		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):
		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))
		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):
		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):
		n = len(M)
		seen = set()
		groups = 0
		for idx in range(n):
			if idx not in seen:
				groups += 1
				seen.add(idx)
				front = {idx}
				while len(front) > 0:
					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):
		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 Solution(object):

	def findCircleNum(self, M):
		seen = set()

		def dfs(n):
			if n in seen:
				return
			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
				dfs(i)
		return count


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 Solution:

	def findCircleNum(self, M):
		if M == None:
			return 0
		n = len(M)
		map1 = [[] for x in range(n)]
		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)
		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