Solution 1:hash table+DFS with iteration

```
def findCircleNum(self, M):
record,res=[0]*len(M),0
for i in range(len(record)):
if record[i]==1:continue #if record[i]==1,means node i has been visited
record[i],t,res=1,[i],res+1 #nodes in 't' are connected with i
for n in t: #DFS with iteration
for j in range(len(M[n])):
if record[j]!=1 and M[n][j]==1:t.append(j)
record[n]=1
return res
```

Solution 2:union find

```
def findCircleNum(self, M):
id,sz,res=[i for i in range(len(M))],[1 for i in range(len(M))],len(M)
def find(i): #quick find
while i!=id[i]:
id[i]=id[id[i]]
i=id[i]
return i
for i in range(len(M)): #quick union
for j in range(len(M[i])):
if i!=j and M[i][j]==1:
it,jt=find(i),find(j)
if it!=jt:
res-=1
if sz[it]<sz[jt]:id[it]=jt;sz[jt]+=sz[it]
else:id[jt]=it;sz[it]+=sz[jt]
return res
```