Training Site
Sideways banner

Topological Sort

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 2.0 seconds

Write an application to output a topologically ordered list of tasks/events

Input

  • The first line will contain the single number 1 \leq N \leq 30, the number of tasks/events
  • The next N lines will contain a description of each task/event. No description is longer than 50 characters.
  • The remaining lines will contain two numbers s_i and d_i (0 \leq s_i, d_i \lt N) which represents that task s_i has to occur before task d_i.
    • Tasks are numbered from 0 to N-1

Note, to scan until the end of file use

    while (scanf("%d%d", &a, &b) != EOF) {
        // code
    }

or with c++ i/o

    while (cin >> src >> dst){
        // code
    }
  • Sample Input 1

    8
    Get jack out of boot
    Lower car
    Put jack back in boot
    Jack up car
    Remove wheel with flat
    Put wheel with flat in boot
    Get spare wheel out of boot
    Put spare wheel on car
    0 1
    1 2
    0 3
    3 4
    3 7
    6 7
    7 1
    4 5
    4 7
    6 5
    

    Sample Output 1

    Get jack out of boot
    Get spare wheel out of boot
    Jack up car
    Remove wheel with flat
    Put wheel with flat in boot
    Put spare wheel on car
    Lower car
    Put jack back in boot