Cod sursa(job #2698554)

Utilizator dnimaraDan Gabriel Nimara dnimara Data 22 ianuarie 2021 14:41:30
Problema Sortare topologica Scor 80
Compilator py Status done
Runda Arhiva educationala Marime 1.62 kb
from collections import deque

def citire(orientat=True,nume_fisier="sortaret.in"):
    n=0
    la=[]
    with open(nume_fisier) as f:
        linie=f.readline()
        n,m=(int(z) for z in linie.split())
        la=[[] for i in range(n+1)]
        for linie in f:
            x,y=(int(z) for z in linie.split())
            la[x].append(y)
            if not orientat:
                la[y].append(x)
    return n, la


n, la = citire()
# print(n)
# for i in range(n):
#     print(str(i)+": ",end="")
#     print(la[i])



ciclu = False
# nod = -1
# fin = -1

# def DFS(s):
#     print(s, q, la[s])
#     viz[s] = 1
#     if flag[s] == -1:
#         flag[s] = 0
#         q.append(s)
#     global ciclu, varf, c
#     for y in la[s]:
#         print(s, la[s])
#         if viz[y] == 1 and flag[y] == 0:
#             if ciclu == False:
#                 ciclu = True
#                 c=[y]
#                 varf=s
#                 print(flag[y],flag[s])
#         elif viz[y] == 0:
#             tata[y] = s
#             d[y] = d[s] + 1
#             DFS(y)
#     if la[s]==[]:
#         q.remove(s)
#         flag[s] = 1
#         DFS(q[len(q)-1])
ciclu=False

def DFS(i, q, viz):
    viz[i] = 1
    for v in la[i]:
        if viz[v] == 0:
            DFS(v, q, viz)
    q.append(i)


viz = [0] * (n + 1)
q = deque()
for i in range(1, n+1):
    if viz[i] == 0:
        #q = deque()
        #q.append(i)
        #viz[i]=1
        DFS(i, q, viz)

with open("sortaret.out","w") as g:
    if not ciclu:
        q.reverse()
        for i in q:
            g.write(str(i)+" ")