擅长:python、mysql、java
<p>我努力想弄明白,但只有在我尝试了伊恩的答案后(谢谢!)建议我认识到理论上的问题是:输入是一个边的列表并定义一个图。我们正在寻找这个图的强连通分量。就这么简单。在</p>
<p>虽然您可以<a href="http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm" rel="noreferrer">do this efficiently</a>,但实际上没有理由自己实现它!只需导入<a href="http://networkx.lanl.gov/" rel="noreferrer">good graph library</a>:</p>
<pre><code>import networkx as nx
# one of your examples
g1 = nx.Graph([(1,3), (15,21), (1,10), (57,66), (76,85), (66,76)])
print nx.connected_components(g1) # [[57, 66, 76, 85], [1, 10, 3], [21, 15]]
# my own test case
g2 = nx.Graph([(1,2),(2,10), (20,3), (3,4), (4,10)])
print nx.connected_components(g2) # [[1, 2, 3, 4, 10, 20]]
</code></pre>