"""

For every person #[1]

We use `dfs()` to traverse all its network and mark all the visited people. #[2]

So if the someone is visited, this means that he/she is in other people's friend cicle already. #[3]

So If Bob is never visited, `circles` adds 1 to represent all the people in the new network. #[4]

Time Complexity is O(N^2), we at most travel every node in the 2D array.

Space Complexity is O(N).

"""

class Solution(object):

def findCircleNum(self, M):

def dfs(i):

stack = [i]

while stack and len(stack)>0:

node = stack.pop()

visited.add(node) #[2]

for j in xrange(len(M)):

if M[node][j]==1 and j not in visited:

stack.append(j)

circles = 0

visited = set()

for i in xrange(len(M)): #[1]

if i in visited: continue #[3]

dfs(i)

circles+=1 #[4]

return circles

"""

We use the `roots` to store every node's root.

So if at index 1 value is 5, means that node1's root is node5. #[1]

We use `find()` to find a node's root by finding the node's parent and parent's parnet... #[2]

Along the way, we also update all the node we encounter.

This technique is also called path compression.

So for every connection, we `union()`, making those two node and all of their parent point to the same root. #[3]

All the children under the root is in the same friend circle.

At last, we count how many unique root in `roots`. #[4]

When we `find()`, we only update all the node's parents until we reach the root. #[5]

We did not update the node's child.

That is why we need to `find()` every node again.

To make sure all nodes in the `roots` has the right value.

Time Complexity is O(N^2) for `find()` is really close to O(1) in average.

Space Complexity is O(N)

"""

class Solution(object):

def findCircleNum(self, M):

def find(x):

if x != roots[x]:

roots[x] = find(roots[x])

return roots[x]

def union(p1, p2): #[2]

p1_root = find(p1)

p2_root = find(p2)

roots[p1_root] = p2_root

roots = [i for i in xrange(len(M))] #[1]

for p1 in xrange(len(M)):

for p2 in xrange(len(M)):

if M[p1][p2] == 1:

union(p1, p2) #[3]

roots = [find(i) for i in roots] #[5]

return len(set(roots)) #[4]

M = [[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]]

s = Solution()

s.findCircleNum(M)