Cod sursa(job #2797450)

Utilizator lazarstefania63@yahoo.comLazar Stefania [email protected] Data 9 noiembrie 2021 21:57:52
Problema Sortare topologica Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 2.4 kb
import copy
import sys

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()]
        if x in adj_list:
            if y not in adj_list[x]:
                add_edge(x, y, adj_list)  # graph is oriented
        else:
            add_edge(x, y, adj_list)
    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))