Two solutions


  • 0
    E

    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
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.