Pagini recente » Cod sursa (job #735731) | Monitorul de evaluare | Cod sursa (job #1798843) | Cod sursa (job #221018) | Cod sursa (job #2698740)
import math
# Complexitate: O(N+M)
def createLists(oriented=False):
global n, m
f = open("sortaret.in", "r")
n, m = [int(x) for x in f.readline().split()]
AdjacentList = [[] for i in range(n)]
for i in range(m):
aux = [int(x) for x in f.readline().split()]
AdjacentList[aux[0] - 1].append(aux[1])
if not oriented:
aux.reverse()
AdjacentList[aux[0] - 1].append((aux[1]))
for i in range(len(AdjacentList)):
AdjacentList[i].sort()
return AdjacentList
def topologicalSort(node):
global stack, viz
viz[node - 1] = 1
for vecin in AdjacentLists[node - 1]:
if viz[vecin - 1] == 0:
topologicalSort(vecin)
stack.append(node)
oriented = True
AdjacentLists = createLists(oriented)
viz = [0 for i in range(n)]
stack = []
for i in range(1, n+1):
if viz[i - 1] == 0:
topologicalSort(i)
stack.reverse()
with open("sortaret.out","w") as g:
for node in stack:
g.write(str(node)+" ")