Non-graph Python solution


  • 0
    class Solution(object):
        def findCircleNum(self, M):
            N = len(M)
            fc = []
            dic = {}
            l = 0
            for i in xrange(N):
                dic[i] = -1
            for i in xrange(N):
                for j in xrange(i+1, N):
                    if M[i][j]==1:
                        if (not dic[i]==-1) or (not dic[j]==-1):
                            if (not dic[j]==-1) and (not dic[i]==-1):
                                if not dic[i]==dic[j]:
                                    tmp = fc[dic[j]]
                                    fc[dic[j]]=[]
                                    fc[dic[i]] += tmp
                                    for f in tmp:
                                        dic[f]=dic[i]
                            else:
                                if (not dic[i]==-1):
                                    fc[dic[i]].append(j)
                                    dic[j]=dic[i]
                                else:
                                    fc[dic[j]].append(i)
                                    dic[i]=dic[j]
                        else:
                            dic[i]=len(fc)
                            dic[j]=len(fc)
                            fc.append([i,j])
                if dic[i]==-1:
                    l += 1
            l += len([f for f in fc if len(f)>0])
            return l
    

Log in to reply
 

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