拓扑排序
* * * *
拉格朗日计划
* * * *
拓扑排序

给定有向图的边,打印其顶点的拓扑排序。

顶点不超过过10个,用0到9之间的数字表示。每条边单独一行,形式为“a b”,表示从a到b的边,同时本题的数据保证顶点序列唯一。

对每条输入数据,输出一个形如"a b c...",表示排序后的顶点为a,b,c,...

本题难度:



解答

用标准算法每次输出入度最小的顶点,本题没有找到太多压缩代码的手段。

最终代码有十行。

代码长度:222字节 vs. 全站第一:95字节。

import sys
for s in sys.argv[1:]:
  d,r={},[]
  for u,_,v in s.split('\n'):d[v]=d.get(v,set())|{u};d[u]=d.get(u,set())
  while d:
    t,u=min((len(x),v)for v,x in d.items())
    r+=[u]
    del d[u]
    for v in d:d[v]-={u}
  print(*r)