使用Kosaraju算法的图中强连通分量的大小（边数）

Question

我已经用python3编写了Kosaraju的两遍算法，当前的实现找到SCC并根据每个SCC中的节点数确定每个SCC的大小。然后，确定最大的scc。如何更改代码，以便它可以根据每个SCC中的边数计算每个SCC的大小。在

# Input : a directed graph, G
import sys, threading, time


# Increase recursion limit and stack size in windows environment
sys.setrecursionlimit(2 ** 20)
threading.stack_size(67108864)


# Source file has one directed edge per line
# e.g. "1 5" is one line. 1 is the tail and 5 is the head
source = "???.txt"
# Number of nodes
n = ???


def main():
    def Kosaraju(G,G_rev):
        global leader, finish
        # Set leader for strongly connected group
        leader = {}
        # Set finishing time for each element
        finish = {}
        # Run first DFS Loop
        DFS_Loop(G_rev)
        # Reorder graph with nodes numbered according to finish time
        G_reordered = {}
        g_values = list(G.values())
        for i in range(1,n+1):
            temp = g_values[i-1]
            G_reordered[finish[i]] = [finish[x] for x in temp]
        # Run second DFS Loop with reordered graph
        DFS_Loop(G_reordered)
        return leader

    def DFS_Loop(G):
        global t,s, explored
        t = 0 # Number of nodes processed so far (only useful for pass 1)
        s = 0 # Current source vertex (only useful for pass 2)
        # Initialize all nodes as unexplored
        explored = {}
        for i in range(1,n+1):
            explored[i] = 0 
        # Explore each adjacent node i (if unexplored)
        for i in range(n,0,-1):
            if explored[i] == 0:
                s = i
                DFS(G,i)
        return

    def DFS(G,i):
        # Run Depth First Search
        global t, leader, finish
        explored[i] = 1 # Mark node i as explored
        leader[i] = s # Sets leader as node s (useful for second pass only)
        # For each arc (i,j) in G, if j is not yet explored, recurse on j
        for j in G[i]:
            if explored[j] == 0:
                DFS(G,j)
        t = t + 1
        finish[i] = t
        return

    def get_graph():
        # Grabs graph from input file
        # Create dictionary with a key for each node
        G, G_rev = {}, {}
        for i in range(1,n+1):
            G[i], G_rev[i]  = [], []
        # Populate dictionary with information from file
        file = open(source)
        for line in file:
            list_line = line.split()
            i = int(list_line[0])
            j = int(list_line[1])
            G[i].append(j)
            G_rev[j].append(i)
        file.close()
        return G, G_rev

    def most_common(lst,x):
        # This functions returns the 'x' most common elements from 'lst' 
        from collections import Counter
        c = Counter(lst)
        output = []        
        for number,count in c.most_common(x):
            output.append(count)
        return output               

    if __name__=="__main__":
        G, G_rev = get_graph()
        leader = Kosaraju(G,G_rev)
        print(most_common(leader.values(),x))


thread = threading.Thread(target=main)
thread.start()

例如，对于图as（以下为列表列表，仅为简单起见）： [[1,2]，[2,3]，[2,5]，[3,4]，[4,1]，[5,6]，[6,7]，[7,5]] 第一个元素是尾部，第二个元素是头部。在

上述代码的结果，包括SCC大小（按降序排列）为[4,3]

但是，当前实现的结果与以下图形相同： [[1,2]，[1,3]，[2,3]，[2,5]，[3,4]，[4,1]，[5,6]，[6,7]，[7,5]] 有额外的边缘[1,3]。我想得到[5,3]作为结果。任何帮助都是非常感谢的。在