Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Graphs

Topological Sort

Medium · Graphs · Asked at Amazon, Microsoft, Google, Flipkart

The directed graph is acyclic. Print a topological order (every edge u → v has u before v). Among all valid orders, print the lexicographically smallest one.

Input

First line: n m. Next m lines: u v — an edge from u to v.

Output

The order, space-separated.

Constraints

Kahn's algorithm with a min-heap instead of a queue: always take the smallest available node.

Example 1

Input

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

Output

5 6 1 3 4 2

Example 2

Input

3 0

Output

1 2 3

Hints

  1. Kahn's algorithm outputs nodes whose prerequisites are all done (in-degree 0).
  2. When several nodes are available, always take the smallest — use a min-heap instead of a queue.

Approach

Compute in-degrees and put all in-degree-0 nodes into a min-heap. Pop the smallest, append it to the order, and decrement its neighbours' in-degrees, pushing those that become 0. Choosing the smallest available node at every step yields the lexicographically smallest topological order (a greedy exchange argument: any other choice puts a larger number at that position).

Complexity: O((n + m) log n) time · O(n + m) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    vector<int> indeg(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        indeg[v]++;
    }
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int v = 1; v <= n; v++)
        if (!indeg[v]) pq.push(v);
    vector<int> order;
    while (!pq.empty()) {
        int u = pq.top();
        pq.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--indeg[v] == 0) pq.push(v);
    }
    for (size_t i = 0; i < order.size(); i++) cout << order[i] << (i + 1 < order.size() ? " " : "\n");
    return 0;
}

Python solution

import sys
import heapq

data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
adj = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for i in range(m):
    u, v = data[2 + 2 * i], data[3 + 2 * i]
    adj[u].append(v)
    indeg[v] += 1
heap = [v for v in range(1, n + 1) if indeg[v] == 0]
heapq.heapify(heap)
order = []
while heap:
    u = heapq.heappop(heap)
    order.append(u)
    for v in adj[u]:
        indeg[v] -= 1
        if indeg[v] == 0:
            heapq.heappush(heap, v)
print(*order)

Java solution

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[n + 1];
        for (int i = 0; i < m; i++) {
            in.nextToken();
            int u = (int) in.nval;
            in.nextToken();
            int v = (int) in.nval;
            adj.get(u).add(v);
            indeg[v]++;
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int v = 1; v <= n; v++) if (indeg[v] == 0) pq.add(v);
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            int u = pq.poll();
            sb.append(sb.length() > 0 ? " " : "").append(u);
            for (int v : adj.get(u)) if (--indeg[v] == 0) pq.add(v);
        }
        System.out.println(sb);
    }
}

Solve Topological Sort online · All practice problems