1008. The Arrow to Remove From a Near-Tree

A chart has n nodes and n ARROWS, each pointing from one node to a different node. It was built by taking a ROOTED TREE, in which exactly one node has no arrow pointing into it and every other node has exactly one, and every node is reachable from that root by following arrows, and then adding one extra arrow.

Remove one arrow so that what is left is a rooted tree again. If more than one arrow would do, remove the one that appears LAST in the input.

Print the two ends of the removed arrow, in the order the input gave them.

n = 3, arrows 1->2, 1->3, 2->3 -> 2 3 n = 3, arrows 1->2, 2->3, 3->1 -> 3 1 n = 4, arrows 2->1, 3->1, 4->2, 1->4 -> 2 1 n = 4, arrows 1->2, 2->3, 3->4, 4->2 -> 4 2

The third chart is the one to work through. Node 1 has two arrows into it, 2->1 at position 1 and 3->1 at position 2, and one of those two is the extra one. Removing the later, 3->1, leaves 2->1, 4->2, 1->4, which is a ring and not a tree at all. So the earlier one has to go, and the answer is 2 1 even though 3->1 appears later.

The fourth chart looks the same at a glance and is not. Node 2 has arrows in from position 1 and position 4; removing the later one leaves 1->2, 2->3, 3->4, a tree rooted at 1, so the later one is taken and the answer is 4 2.

## Two things can go wrong, and only two

Adding one arrow to a rooted tree breaks it in one of two ways.

Some node ends with two arrows into it. The extra arrow is one of those two and nothing else, because every other node still has the one arrow the tree gave it. Call the earlier of the two A and the later B.

No node has two arrows into it. Then every node has exactly one, the arrow counts add up, and the chart is a single directed loop with trees hanging off it. Every arrow ON the loop may be removed, and no arrow off it may be.

## Deciding between A and B

Prefer B, because it is later in the input. Test it: delete B and feed the remaining n - 1 arrows to a disjoint set, IGNORING their direction. If some arrow joins two nodes already connected, the rest still holds a loop, so B was the wrong one to take and the answer is A. Otherwise the answer is B.

That test is enough because after deleting one of the two arrows into the doubled node, every node has at most one arrow into it and there are n - 1 arrows on n nodes. Such a chart is a rooted tree exactly when its undirected form has no loop, which is what the disjoint set reports.

## The loop case

With no doubled node, run the same disjoint set over all n arrows in input order. The first arrow that joins two already-connected nodes is the one that closes the loop, and it is the LAST arrow of that loop to appear in the input, since a loop is only complete when its final arrow arrives. Every loop arrow is removable, so the last one is the answer.

## The boundary

Two nodes with arrows both ways, 1->2 and 2->1, is the smallest possible chart. It has no node with two arrows in, so it is the loop case, and the answer is the second arrow.

## Cross-reference

Problem 387 removes the last redundant edge of an UNDIRECTED graph, where "already connected" is the whole story. Direction is what makes this harder: an undirected disjoint set cannot see that a node has two arrows into it, so the arrow count has to be tracked separately and the structure is used only for the loop half of the test.

## Cost

Time O(n alpha(n)), with the structure rebuilt at most twice. Space O(n).

Constraints - `2 ≤ n ≤ 1000` - There are exactly `n` arrows. - `1 ≤ u, v ≤ n` and `u` is never equal to `v`. - The arrows are a rooted tree on the `n` nodes with one extra arrow added.