Pagini recente » Cod sursa (job #1301525) | Cod sursa (job #2057551) | Cod sursa (job #1490387) | Cod sursa (job #2672045) | Cod sursa (job #2797597)
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()