Minimal Labels (Codeforces 825E)
Tags: Greedy, dfs and similar

You are given a directed acyclic graph with n vertices and m edges. There are no self-loops or multiple edges between any pair of vertices. Graph can be disconnected.You should assign labels to all vertices in such a way that:  Labels form a valid permutation of length n — an integer sequence such that each integer from 1 to n appears exactly once in it.  If there exists an edge from vertex v to vertex u then labelv should be smaller than labelu.  Permutation should be lexicographically smallest among all suitable. Find such sequence of labels to satisfy all the conditions.

Input: The first line contains two integer numbers n, m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105).Next m lines contain two integer numbers v and u (1 ≤ v, u ≤ n, v ≠ u) — edges of the graph. Edges are directed, graph doesn't contain loops or multiple edges.

Output: Print n numbers — lexicographically smallest correct permutation of labels of vertices.


Sample Inputs:
3 3
1 2
1 3
3 2

4 5
3 1
4 1
2 3
3 4
2 4

5 4
3 1
2 1
2 3
4 5

Sample Outputs:
1 3 2

4 1 2 3

3 1 2 4 5

Solution (Python):
from collections import defaultdict
import sys, threading
import heapq
_input = sys.stdin.readline
hpop = heapq.heappop
hpush = heapq.heappush

def _print(*argv, sep=' '):
    sys.stdout.write(sep.join(map(str, argv)) + '\n')

def outbool(val):
    return 'YES' if val else 'NO'

def inp():
    return int(_input())

def inlt():
    return list(map(int, _input().split()))

def insr():
    s = _input()
    return list(s.strip())

def invr():
    return map(int, _input().split())

def solve():
    (n, m) = invr()
    graph = defaultdict(list)
    incoming = [0] * (n + 1)
    for _ in range(m):
        (u, v) = invr()
        graph[v].append(u)
        incoming[u] += 1
    heap = []
    for i in range(1, n + 1):
        if incoming[i] == 0:
            hpush(heap, -i)
    ans = [0] * n
    curr = n
    while heap:
        u = hpop(heap)
        u = -u
        ans[u - 1] = curr
        curr -= 1
        for v in graph[u]:
            incoming[v] -= 1
            if incoming[v] == 0:
                hpush(heap, -v)
    _print(*ans)

def main():
    t = 1
    for _ in range(t):
        solve()
if __name__ == '__main__':
    sys.setrecursionlimit(1 << 30)
    threading.stack_size(1 << 27)
    main_thread = threading.Thread(target=main)
    main_thread.start()
    main_thread.join()

Solution (Python):
(n, m) = map(int, input().split())
d = [0] * n
e = [[] for i in range(n)]
for i in range(m):
    (u, v) = map(int, input().split())
    u -= 1
    v -= 1
    d[u] += 1
    e[v].append(u)
from heapq import heappush, heappop
pq = []
for i in range(n):
    if d[i] == 0:
        heappush(pq, -i)
ind = n
ans = [0] * n
while pq:
    u = -heappop(pq)
    ans[u] = ind
    ind -= 1
    for v in e[u]:
        d[v] -= 1
        if d[v] == 0:
            heappush(pq, -v)
print(' '.join((str(x) for x in ans)))

Solution (Python):
from collections import defaultdict
import heapq
(n, m) = map(int, input().split())
graph = defaultdict(list)
indegree = {i: 0 for i in range(1, n + 1)}
ans = [0] * n
for _ in range(m):
    (v, u) = map(int, input().split())
    graph[u].append(v)
    indegree[v] += 1
queue = [-i for i in indegree if indegree[i] == 0]
heapq.heapify(queue)
label = n
while queue:
    node = heapq.heappop(queue)
    node = -1 * node
    ans[node - 1] = str(label)
    label -= 1
    for neigh in graph[node]:
        indegree[neigh] -= 1
        if indegree[neigh] == 0:
            heapq.heappush(queue, -neigh)
print(' '.join(ans))