Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.2 kB
3
Indexable
Never
import sys
import math
from  collections import defaultdict, Counter, deque
from heapq import heapify, heappop, heappush


# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')


def topo_sort(node, adj_list, res, visited, parent):
    visited.add(node)

    for adj_node in adj_list[node]:
        if adj_node not in visited:
            topo_sort(adj_node, adj_list, res, visited, node)
        if adj_node == parent:
            res.append(adj_node)

    res.append(node)



def main():
    [n, m] = list(map(int, input().split()))

    edge_list = []
    for _ in range(n):
        edge = input().split()
        edge_list.append(edge)

    adj_list = defaultdict(list)

    for edge in edge_list:
        [u, v] = edge
        adj_list[u].append(v)

    for node in adj_list:
        adj_list[node] = sorted(adj_list[node], reverse=True)

    visited = set()

    topo_sort_res = []
    
    topo_sort("ABC", adj_list, topo_sort_res, visited, -1)

    nodes = sorted(adj_list.keys())
    for node in nodes:
        if node != "ABC" and node not in visited:
            topo_sort("ABC", adj_list, topo_sort_res, visited, -1)


    ans = ' '.join(topo_sort_res[::-1])
    print(ans)








main()
Leave a Comment