```
class Solution(object):
def find(self, i):
v = self.dic[i]
if v == i: #the root
return i
else:
r = self.find(v) #find root type, collapse route
self.dic[i] = r
return r
def union(self, i, j): #union
if self.find(i) != self.find(j):#union two different types, just union two roots
self.dic[self.dic[i]] = self.dic[j]
def findCircleNum(self, M):
"""
:type M: List[List[int]]
:rtype: int
"""
self.dic = {} #k:friend_id,v:type
for i in range(len(M)):
self.dic[i] = i #init with different types, all is root.
for i,l in enumerate(M):
j = i + 1 #the left top half of matrix would be enough
while j < len(M):
if l[j] == 1:
self.union(i, j)
j += 1
s = set()
for i in range(len(M)): #find all types
s.add(self.find(i))
return len(s)
```