題目：
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
思路：
1.這題的知識(shí)點(diǎn)其實(shí)是Union-Find赁炎，我只用了DFS的方法寫了甘邀，二刷的時(shí)候還要看Union-Find的方法去解垮庐。
Python
class Solution(object):
def findCircleNum(self, M):
"""
:type M: List[List[int]]
:rtype: int
"""
count = 0
visited = [0] * len(M)
for i in xrange(len(M)):
if not visited[i]:
visited[i] = 1
self.dfs(M, visited, i)
count += 1
return count
def dfs(self, M, visited, i):
for j in xrange(len(M)):
if M[i][j] and not visited[j]:
visited[j] = 1
self.dfs(M, visited, j)
