python で強連結成分分解

ライブラリnetworkxを使うと簡単。

import networkx as nx
G=nx.read_edgelist("test.net",create_using=nx.DiGraph())
j=nx.strongle_connected_components(G)
l=0
for i in j:
    for k in i:
       print k,l;
    l=l+1;

最大強連結成分の抜き出し。

import networkx as nx
G=nx.read_edgelist("test.net",create_using=nx.DiGraph())
j=nx.strongle_connected_components(G)
l=0
print "#nodes"
for i in j:
    for k in i:
       print k,l;
　　if(l!=0):
       G.remove_nodes_from(i)
    l=l+1;

print "#edge"
for i in G.edges():
      print i[0],i[1]