Graph (Editorial)

The lexicographically smallest topological sort is built by Kahn's algorithm with a priority queue: at each step, among all available vertices (vertices that have no incoming edges from vertices not yet written out), the vertex with the smallest number is chosen.

An added edge $u \to v$ u \to v makes the vertex $v$ unavailable until the vertex $u$ is written out. So by adding edges we can "hide" small vertices and thereby force the algorithm to choose vertices with larger numbers. Each hidden vertex costs one edge from the budget $k$ .

The greedy idea. We build the answer position by position. Lexicographic comparison is decided by the first differing position, so at each position we must place the vertex with the largest possible number — no gains at later positions can compensate for a loss at the current one.

We divide the vertices that can be written out at the current step into two sets:

$A$ — the available vertices: all edges entering them have already been "removed". If we do nothing, Kahn's algorithm chooses the smallest vertex of $A$ ;
$B$ — the deferred vertices. These are vertices that were available, but we decided to hide them. For each such vertex we commit to adding an edge entering it. We choose the start of this edge later — it will be the vertex written out immediately before the deferred one.

The set $A$ is stored in a priority queue with the smallest element on top (a min-heap), and the set $B$ in a priority queue with the largest element on top (a max-heap).

When it pays to defer a vertex. Let $x$ be the smallest vertex in $A$ . If we leave it alone, $x$ will be placed at the current position. Deferring $x$ (spending an edge) makes sense in two cases:

$A$ contains at least two vertices. Then, after $x$ is deferred, the next vertex of $A$ in increasing order, which is greater than $x$ , will be placed at the current position;
$A$ contains only the vertex $x$ , but $B$ contains a deferred vertex $y > x$ y > x. Then, after $x$ is deferred, the set $A$ becomes empty, and the largest deferred vertex — a number greater than $x$ — will be placed at the current position.

In all other cases deferring does not increase the number at the current position, and there is no need to spend an edge. We defer vertices one at a time, starting with the smallest, as long as it pays off and the budget $k$ is not exhausted.

Which vertex to write out. After deferring:

if $A$ is not empty, we write out the smallest vertex of $A$ — this is required by the rule of the lexicographically smallest sort;
if $A$ is empty, we write out the largest deferred vertex $v$ from $B$ and add an edge from the last written vertex to $v$ . It is exactly this edge that "hid" the vertex $v$ : until now it was unavailable, and now, when its new predecessor has been written out, it becomes the only available vertex. The other deferred vertices remain hidden — their edges will be added later.

Then, as usual in Kahn's algorithm, we decrease the in-degrees of the neighbours of the written vertex; vertices whose in-degree becomes zero are added to $A$ .

Why the answer is correct. Every deferred vertex is sooner or later written out from $B$ , and exactly one edge is added at that moment. Therefore the number of added edges equals the number of deferrals and does not exceed $k$ . All added edges go from a vertex written out earlier to a vertex written out later, so the found order is a topological sort of the new graph and no cycles appear.

Complexity. Each vertex enters $A$ at most once and $B$ at most once, and each edge of the graph is examined once. The total complexity is $O ((n + m) lo g n)$ O((n + m) \log n).

Algorithm for Solving the Problem

We use Kahn's algorithm and two priority queues:

$A$ — min-heap that stores available vertices, with the smallest-numbered vertex at the top.
$B$ — max-heap that stores deferred vertices, with the largest-numbered vertex at the top.

Declare the following arrays:

$in d e g [v]$ indeg[v] — the number of incoming edges of vertex $v$ that have not yet been processed;
$an s$ — the resulting topological ordering;
$e d g es$ — the list of added edges.

Step 1. Initialization

Compute the in-degree of every vertex.
Add all vertices with zero in-degree to $A$ .
Initialize $B$ and the list $e d g es$ as empty.

Step 2. Constructing the Answer

While not all $n$ vertices have been processed:

1. Defer a vertex if it is beneficial.

While the number of added edges is less than $k$ , heap $A$ is not empty, and at least one of the following conditions holds:

$A$ contains at least two vertices;
$A$ contains a single vertex $x$ , and $B$ contains a vertex $y$ such that $y > x$ y > x.

Extract the smallest vertex $x$ from $A$ and insert it into $B$ . This vertex will be processed later.

2. Choose the Next Vertex.

If $A$ is not empty, extract the smallest vertex $v$ from it.
Otherwise, extract the largest vertex $v$ from $B$ . If $an s$ is not empty, add an edge from the last vertex in $an s$ to $v$ .

Append $v$ to the end of $an s$ .

3. Update the Graph.

For each outgoing edge $v \to u$ v \to u:

Decrease $in d e g [u]$ indeg[u] by one.
If $in d e g [u]$ indeg[u] becomes zero, add $u$ to $A$ .

Repeat these steps until all vertices have been added to $an s$ .

Step 3. Output

Print the sequence $an s$ .
Print the number of added edges.
Print the added edges themselves.

Example

Consider the example from the statement: $n = 5$ n = 5, $k = 2$ k = 2, edges $1 \to 4$ 1 \to 4, $4 \to 2$ 4 \to 2, $1 \to 3$ 1 \to 3. Initial in-degrees: vertices $1$ and $5$ have in-degree $0$ , vertices $2, 3, 4$ have in-degree $1$ . The initial sets are $A = {1, 5}$ A = \{1, 5\}, $B = {}$ B = \{\,\}.

Step	Deferred	$A$	$B$	$k$	Take	Edge	Order
$1$	$1$ (two vertices in $A$ )	${5}$	${1}$	$1$	$5$ from $A$	—	$5$
$2$	—	${}$	${1}$	$1$	$1$ from $B$	$5 \to 1$ 5 \to 1	$5, 1$
$3$	$3$ (two vertices in $A$ : $3$ and $4$ )	${4}$	${3}$	$0$	$4$ from $A$	—	$5, 1, 4$
$4$	— ( $k = 0$ k = 0)	${2}$	${3}$	$0$	$2$ from $A$	—	$5, 1, 4, 2$ 5, 1, 4, 2
$5$	—	${}$	${3}$	$0$	$3$ from $B$	$2 \to 3$ 2 \to 3	$5, 1, 4, 2, 3$ 5, 1, 4, 2, 3

Let us go through the steps in more detail.

Step 1. $A = {1, 5}$ A = \{1, 5\} contains two vertices, so we defer the smallest one — $1$ . Now $A = {5}$ A = \{5\} contains one vertex, and $B$ has no vertices greater than $5$ , so we stop deferring. We write out $5$ .
Step 2. $A$ is empty. We write out the largest deferred vertex $1$ and add the edge $5 \to 1$ 5 \to 1. We remove the edges $1 \to 4$ 1 \to 4 and $1 \to 3$ 1 \to 3: vertices $4$ and $3$ become available, $A = {3, 4}$ A = \{3, 4\}.
Step 3. $A$ contains two vertices — we defer $3$ , and the edge budget is exhausted ( $k = 0$ k = 0). We write out $4$ , after which the edge $4 \to 2$ 4 \to 2 is removed and $A = {2}$ A = \{2\}.
Step 4. No more deferrals are possible. We write out $2$ .
Step 5. $A$ is empty. We write out the deferred vertex $3$ and add the edge $2 \to 3$ 2 \to 3.

We obtain the order $5, 1, 4, 2, 3$ 5, 1, 4, 2, 3 and the added edges $5 \to 1$ 5 \to 1 and $2 \to 3$ 2 \to 3. The original graph (left) and the graph with the added edges (right, the added edges are shown in red):

Without added edges the lexicographically smallest sort is $1, 3, 4, 2, 5$ 1, 3, 4, 2, 5: vertex $5$ is not connected to anything, but because of its large number it is chosen last. After two edges are added, vertex $5$ comes first, and the order $5, 1, 4, 2, 3$ 5, 1, 4, 2, 3 is lexicographically larger.

Consider one more example, in which four vertices are available at the beginning. Let $n = 8, m = 6, k = 4$ n = 8, m = 6, k = 4, and let the edges of the graph be $6 \to 3, 4 \to 8, 3 \to 5, 1 \to 7, 2 \to 7, 5 \to 7$ 6 \to 3, 4 \to 8, 3 \to 5, 1 \to 7, 2 \to 7, 5 \to 7.

No edge enters vertices $1, 2, 4, 6$ 1, 2, 4, 6, so at the beginning $A = {1, 2, 4, 6}$ A = \{1, 2, 4, 6\}, $B = {}$ B = \{\,\}. Without added edges the lexicographically smallest sort is $1, 2, 4, 6, 3, 5, 7, 8$ 1, 2, 4, 6, 3, 5, 7, 8.

The original graph (left) and the graph after adding edges (right, the added edges are shown in red)

Step	$A$ before	$B$ before	$k$	Deferred	Take	Edge
$1$	${1, 2, 4, 6}$ \{1, 2, 4, 6\}	${}$	$4$	$1, 2, 4$	$6$ from $A$	—
$2$	${3}$	${4, 2, 1}$ \{4, 2, 1\}	$1$	$3 (4 > 3)$ 3~(4 > 3)	$4$ from $B$	$6 \to 4$ 6 \to 4
$3$	${8}$	${3, 2, 1}$ \{3, 2, 1\}	$0$	—	$8$ from $A$	—
$4$	${}$	${3, 2, 1}$ \{3, 2, 1\}	$0$	—	$3$ from $B$	$8 \to 3$ 8 \to 3
$5$	${5}$	${2, 1}$	$0$	—	$5$ from $A$	—
$6$	${}$	${2, 1}$	$0$	—	$2$ from $B$	$5 \to 2$ 5 \to 2
$7$	${}$	${1}$	$0$	—	$1$ from $B$	$2 \to 1$ 2 \to 1
$8$	${7}$	${}$	$0$	—	$7$ from $A$	—

Let us go through the steps in more detail.

Step 1. $A = {1, 2, 4, 6}$ A = \{1, 2, 4, 6\}, $k = 4$ k = 4. We defer vertex $1$ , since $A$ contains four vertices, then $2$ (three vertices in $A$ ), then $4$ (two vertices in $A$ ). The budget decreases to $k = 1$ k = 1. Now $A = {6}$ A = \{6\} contains one vertex, and the largest deferred vertex $4$ is less than $6$ — further deferring does not pay off. We write out $6$ . The edge $6 \to 3$ 6 \to 3 is removed, and $A = {3}$ A = \{3\}.
Step 2. $A = {3}$ A = \{3\}, $B = {4, 2, 1}$ B = \{4, 2, 1\}, $k = 1$ k = 1. $A$ contains one vertex, but $B$ contains the vertex $4 > 3$ 4 > 3, so we defer $3$ as well; the budget is exhausted, $k = 0$ k = 0. $A$ is empty — we write out the largest deferred vertex $4$ and add the edge $6 \to 4$ 6 \to 4. The edge $4 \to 8$ 4 \to 8 is removed, and $A = {8}$ A = \{8\}.
Step 3. No more deferrals are possible. We write out $8$ , after which $A$ is empty.
Step 4. We write out the largest deferred vertex $3$ and add the edge $8 \to 3$ 8 \to 3. The edge $3 \to 5$ 3 \to 5 is removed, and $A = {5}$ A = \{5\}.
Step 5. We write out $5$ . The edge $5 \to 7$ 5 \to 7 is removed, but edges from $1$ and $2$ still enter vertex $7$ , so $A$ is empty.
Step 6. We write out the deferred vertex $2$ and add the edge $5 \to 2$ 5 \to 2. The edge $2 \to 7$ 2 \to 7 is removed.
Step 7. We write out the deferred vertex $1$ and add the edge $2 \to 1$ 2 \to 1. The edge $1 \to 7$ 1 \to 7 is removed, and $A = {7}$ A = \{7\}.
Step 8. We write out $7$ .

The answer:

6 4 8 3 5 2 1 7
4
6 4
8 3
5 2
2 1

This example clearly shows all cases of the algorithm. At step $1$ three vertices are deferred at once — as long as $A$ contains at least two vertices. At step $2$ the second condition applies: $A$ contains only vertex $3$ , but $B$ contains the larger vertex $4$ , so $3$ is deferred as well. Deferred vertices leave $B$ in decreasing order $(4, 3, 2, 1)$ (4, 3, 2, 1), and each of them receives exactly one edge from the vertex written out before it. Therefore exactly as many edges are added as there were deferrals — four.

Algorithm implementation

Read the input data. Construct the graph. The adjacency lists are stored in $g$ , the in-degrees in $in d e g$ .

scanf("%d %d %d", &n, &m, &k);
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++)
{
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  indeg[v]++;
}

C++

Declare two priority queues: $A$ — the available vertices, with the smallest element on top (a min-heap); $B$ — the deferred vertices, with the largest element on top (a max-heap).

priority_queue<int, vector<int>, greater<int>> A; // available, min-heap
priority_queue<int> B;                            // deferred, max-heap

Initially all vertices with zero in-degree are available.

for (int v = 1; v <= n; v++)
  if (indeg[v] == 0) A.push(v);

The array $or d er$ accumulates the answer — the required topological sort, and the array $a dd e d$ stores the added edges.

vector<int> order;
order.reserve(n);
vector<pair<int, int>> added;

Each iteration of the loop adds one vertex to the answer, until all $n$ vertices are written out.

while ((int)order.size() < n)
{

Defer vertices. While there are edges left in the budget and the set $A$ is not empty, consider the smallest available vertex $x$ . It pays to defer it if $A$ contains at least one more vertex or if $B$ contains a deferred vertex with a larger number. A deferred vertex is moved from $A$ to $B$ , and the budget $k$ decreases by $1$ . Otherwise deferring stops.

  // defer vertices while it pays off and edges remain
  while (k > 0 && !A.empty())
  {
    int x = A.top();
    if (A.size() >= 2 || (!B.empty() && B.top() > x))
    {
      A.pop();
      B.push(x);
      k--;
    }
    else break;
  }

C++

Choose the vertex $v$ to be written out at the current position. If $A$ is not empty, it is the smallest available vertex. Otherwise we take the largest deferred vertex and add an edge from the last written vertex $or d er . ba c k ()$ order.back() to $v$ .

  int v;
  if (!A.empty())
  {
    v = A.top();
    A.pop();
  }
  else
  {
    v = B.top();
    B.pop();
    added.push_back(make_pair(order.back(), v));
  }

C++

Append $v$ to the answer and, as in Kahn's algorithm, decrease the in-degrees of its neighbours. Vertices whose in-degree becomes zero become available.

  order.push_back(v);
  for (int to : g[v])
    if (--indeg[to] == 0) A.push(to);
}

Print the found topological sort, the number of added edges and the edges themselves.

for (int i = 0; i < n; i++)
  printf("%d ", order[i]);
printf("\n%d\n", added.size());
for (auto &e : added)
  printf("%d %d\n", e.first, e.second);