Proficient.
Put your skills to the test.

Problem summary

Renumber a DAG so vertices sort by the decreasing list of their direct successors’ new numbers. Equal successor sets are ordered by old vertex number.

Constraints

2 ≤ N ≤ 100000; 2 ≤ M ≤ 1000000; input is a DAG.

Worked example

An independently prepared example for this explanation.

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

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

Solution analysis

1. Every successor must receive a smaller new number than its predecessor. Otherwise follow a successor with a larger number repeatedly: its successor-list comparison forces another larger number, contradicting acyclicity. Thus process the graph from sinks backward.
2. A vertex becomes ready once all its successors have numbers. Its comparison key is their numbers sorted decreasingly, followed by its old number as a tie-breaker. Repeatedly assign the next number to the smallest ready key in a priority queue.
3. In the sample, sinks 4,5,6 receive 1,2,3. Vertices 3,1,2 then have keys [2], [2,1], [3,2], giving new numbers 4,5,6. A not-yet-ready vertex has an unnumbered successor and therefore a future key beginning at least as large as the next number; any ready key begins with an already assigned smaller number.

Why it works

The lexicographic rule implies every edge points to a smaller new label: take a vertex of minimum new label violating this, and compare it with its larger-labeled successor; the required decreasing-key order forces a further larger successor, yielding an impossible increasing path. Therefore only ready vertices can be next. Among ready vertices their fully known keys impose their exact relative order. An unready vertex’s maximum successor label is larger than every ready key entry, so it cannot precede the chosen ready minimum. Induction establishes the unique renumbering.

Watch out. Use direct successors from the input edges. Empty lists are lexicographically smallest. A usual minimum-id topological ordering does not implement these list comparisons.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
// Algorithm: Every successor must receive a smaller new number than its predecessor.
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<int>>predecessors(n),key(n);
    vector<int>remaining(n,0),label(n,0);
    for(int i=0;i<m;++i){
        int from,to;
        cin>>from>>to;
        --from;
        --to;
        predecessors[to].push_back(from);
        ++remaining[from];
    }
    auto later=[&](int a,int b){
        if(key[a]!=key[b]){
            return key[a]>key[b];
        }
        return a>b;
    };
    priority_queue<int,vector<int>,decltype(later)>ready(later);
    for(int vertex=0;vertex<n;++vertex){
        if(remaining[vertex]==0){
            ready.push(vertex);
        }
    }
    int nextLabel=0;
    while(!ready.empty()){
        int vertex=ready.top();
        ready.pop();
        label[vertex]=++nextLabel;
        for(int previous:predecessors[vertex]){
            key[previous].push_back(label[vertex]);
            if(--remaining[previous]==0){
                reverse(key[previous].begin(),key[previous].end());
                ready.push(previous);
            }
        }
    }
    for(int vertex=0;vertex<n;++vertex){
        cout<<vertex+1<<' '<<label[vertex]<<'\n';
    }
}