Cod sursa(job #2797597)

Utilizator PopelEmilBogdanPopel Emil-Bogdan PopelEmilBogdan Data 10 noiembrie 2021 11:33:13
Problema Sortare topologica Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.09 kb
from collections import defaultdict

with open("sortaret.in", 'r') as f:
    lines = f.readlines()
    N, M= [int(val) for val in lines[0].split()]
f.close()

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)


    def addEdge(self, u, v):
        self.graph[u].append(v)

    def Top_sort_AUX(self, nod_curr, visited, stack):
        visited[nod_curr] = True

        for i in self.graph[nod_curr]:
            if not visited[i]:
                self.Top_sort_AUX(i, visited, stack)


        stack.insert(0,nod_curr)


    def Topological_Sort(self):
        stack = []
        visited = [False] * (N+1)

        for i in range(1, N+1):
            if not visited[i]:
                self.Top_sort_AUX(i, visited, stack)

        with open("sortaret.out", 'w') as fout:
            for element in stack:
                fout.write('%s ' %element)
        fout.close()



g = Graph()
for i in range(1, M + 1):
    node1, node2 = [int(val) for val in lines[i].split()]
    g.addEdge(node1, node2)
    g.addEdge(node2, node1)
g.Topological_Sort()