Python连接的组件

让我们简化图形表示：

myGraph = {0: [1,2,3], 1: [], 2: [1], 3: [4,5],4: [3,5], 5: [3,4,7], 6: [8], 7: [],8: [9], 9: []}

这里，我们有一个函数返回一个字典，该字典的键是根，值是连接的组件：

def getRoots(aNeigh):    def findRoot(aNode,aRoot):        while aNode != aRoot[aNode][0]: aNode = aRoot[aNode][0]        return (aNode,aRoot[aNode][1])    myRoot = {}     for myNode in aNeigh.keys():        myRoot[myNode] = (myNode,0)      for myI in aNeigh:         for myJ in aNeigh[myI]:  (myRoot_myI,myDepthMyI) = findRoot(myI,myRoot)  (myRoot_myJ,myDepthMyJ) = findRoot(myJ,myRoot)  if myRoot_myI != myRoot_myJ:      myMin = myRoot_myI     myMax = myRoot_myJ      if  myDepthMyI > myDepthMyJ:          myMin = myRoot_myJ         myMax = myRoot_myI     myRoot[myMax] = (myMax,max(myRoot[myMin][1]+1,myRoot[myMax][1]))     myRoot[myMin] = (myRoot[myMax][0],-1)     myToRet = {}    for myI in aNeigh:         if myRoot[myI][0] == myI: myToRet[myI] = []    for myI in aNeigh:         myToRet[findRoot(myI,myRoot)[0]].append(myI)     return myToRet

让我们尝试一下：

print getRoots(myGraph)

{8：[6、8、9]，1：[0、1、2、3、4、5、7]}