2_toposort

2. Determining an Order of Courses

Problem Description

Task. Compute a topological ordering of a given directed acyclic graph (DAG) with n vertices and m edges.

Input Format. An undirected graph with n vertices and m edges. The next line contains two vertices u and v of the graph.

Constraints. 1 ≤ n ≤ 10³; 0 ≤ m ≤ 10³; 1 ≤ u, v ≤ n; u ̸= v.

Output Format. Output any topological ordering of its vertices. (Many DAGs have more than just one topological ordering. You may output any of them.)

Sample 1.

    Input
        4 3
        1 2
        4 1
        3 1
    Output
        4 3 1 2

Sample 2.

    Input
        4 1
        3 1
    Output
        2 3 1 4

Solution

private static ArrayList<Integer> toposort(ArrayList<Integer>[] adj) {
    boolean used[] = new boolean[adj.length];
    ArrayList<Integer> order = new ArrayList<Integer>();

    for (int v = 0; v < adj.length; v++) {
        dfs(adj, used, order, v);
    }
    Collections.reverse(order);
    return order;
}

private static void dfs(ArrayList<Integer>[] adj, boolean[] used, ArrayList<Integer> order, int s) {
    if (used[s])    return;
    used[s] = true;
    for (int w : adj[s]) {
        dfs(adj, used, order, w);
    }
    order.add(s);
}

Test

Compile with javac Toposort.java and run with java Toposort.

This is only for discussion and communication. Please don't use this for submission of assignments.