387. The Edge That Closed the Loop
The edges arrive one at a time, and each one joins two vertices. Print the LAST
edge in the input that joined two vertices already connected to each other, so
removing it would leave the graph exactly as connected as it is now. Print
NONE if no edge ever does that.
Print the edge in the order the input gave it, u then v.
This introduces disjoint set union, also called union-find, and it is the right
tool because the question is asked repeatedly as the graph grows. Keep a
representative for each group. Adding edge u v means finding the
representative of each end: different means the edge joins two groups, so merge
them; the same means both ends were already connected, so this edge is
redundant.
Re-running a traversal after every edge would answer the same question in
O(m × n) instead of very nearly O(m).
The word LAST matters. In a triangle listed 1 2, 2 3, 3 1, the answer is
3 1 and not 1 2.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - There are no self-loops and no repeated edges.
Input
The first line contains two integers n and m, the number of vertices and
edges. Each of the next m lines contains two integers u and v, an
undirected edge between those vertices. Vertices are numbered 1 to n.
Output
Print the two endpoints of the last redundant edge separated by a space, or the
word NONE.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.