# Edges expiring

Given a graph with expiring dates for every edge, when will the graph be disconnected?

### Key observation

The trick is to inverse the time and to add edges to an initial empty graph, in the reverse order they are expiring. Once the current graph is connected you know that the answer is the time of the last added edge. Use union-find to maintain connected components. Hence the problem can be solved in quasi linear time.

### union-find

Union-Find is a data structure which maintains a partition. Every set in the partition corresponds to a connected component. Initially every vertex is a component by itself. *Find(v)* returns a representative of the component containing v. The components are organized as a tree, with the representative as root. The table f contains for every vertex v the father f[v] in that tree. We have f[v]=v iff v is the root of a tree.
Union merges two components by attaching one tree below another. The function *Find(v)* walks all the way from vertex v to the root, and attaches the vertices along the path directly below the root. This flattens the tree.

The following code is simple and could be good enough in practice if you are lucky.

But in order to ensure worst case complexity almost constant for the *Find* and *Union* operation, you need to maintain a rank for each component and attach always the tree with smaller rank below the one with largest.