import copy
adj_list = {}
my_list = []
def add_node(node):
if node not in my_list:
my_list.append(node)
def add_edge(node1, node2, my_graph):
temp = []
if node1 in my_list and node2 in my_list:
if node1 not in my_graph:
temp.append(node2)
my_graph[node1] = temp
elif node1 in my_graph:
temp.extend(my_graph[node1])
temp.append(node2)
my_graph[node1] = temp
def read():
n, m = [int(x) for x in f.readline().split()]
for i in range(1, n + 1):
add_node(i)
for i in range(m):
x, y = [int(z) for z in f.readline().split()]
add_edge(x, y, adj_list) # graph is oriented
return n, m
def graph():
for node in adj_list:
print(node, " ---> ", [i for i in adj_list[node]])
def remove_node(my_graph, delete_value):
if delete_value in my_graph:
del my_graph[delete_value]
for edges in my_graph.values():
copy_edge = copy.deepcopy(edges)
if delete_value in copy_edge:
edges.remove(delete_value)
def find_topological_order(my_graph):
incoming_degree = {}
topological_queue = []
topological_order = []
for node in my_list:
incoming_degree[node] = 0
for edges in my_graph.values():
for edge in edges:
incoming_degree[edge] += 1
while adj_list:
for node, income in incoming_degree.items():
if income == 0:
topological_queue.append(node)
incoming_degree[node] = -1
while topological_queue:
node_to_remove = topological_queue.pop(0)
topological_order.append(node_to_remove)
if node_to_remove in adj_list:
for edge in my_graph[node_to_remove]:
incoming_degree[edge] -= 1
remove_node(my_graph, node_to_remove)
for node, income in incoming_degree.items():
if income == 0:
topological_order.append(node)
return topological_order
f = open("sortaret.in", "r")
f_out = open("sortaret.out", "w")
N, M = read()
my_topological_order = find_topological_order(adj_list)
f_out.write(" ".join(str(y) for y in my_topological_order))