996. How Deep the Chains Get
This problem asks you to SIMULATE a disjoint set with both optimisations switched off, and report how badly it degrades.
The structure is exactly this, and nothing else:
``` parent[i] = i for every i from 1 to n
root(x): while parent[x] != x: x = parent[x] no pointer is ever rewritten return x
join(u, v): ru = root(u) rv = root(v) if ru != rv: parent[ru] = rv u's root always goes under v's root ```
There is no path compression and no comparison of sizes. Run the q joins in the order
given, then print the largest number of pointer steps from any element to its root.
n = 5, joins (1 2)(2 3)(3 4)(4 5) -> 4
n = 5, joins (2 1)(3 1)(4 1)(5 1) -> 1
n = 4, joins (1 2)(3 4)(2 4) -> 2
n = 1, no joins -> 0
Follow the first one. join(1,2) sets parent[1] = 2. join(2,3) finds root 2 for the
first argument and sets parent[2] = 3, so 1 is now two steps from the root. join(3,4)
puts 3 under 4, and join(4,5) puts 4 under 5. Element 1 now walks 1, 2, 3, 4, 5: four
steps.
The second one is the same five elements and the same four joins, written the other way
round. join(2,1) sets parent[2] = 1, then 3, 4 and 5 all attach to root 1 directly, and
nothing is ever more than one step from the root.
## What this is measuring
The number printed is the cost of the most expensive root call the structure can be asked
for. Both examples do the same work and both answer the same connectivity questions; one is
four times more expensive to query than the other, purely because of which root was chosen to
survive.
## What most people try first
Recompute the depth of every element after every join. That is O(n) walks each up to
O(n) long, per operation, so O(n^2 q). Walking every element once at the END is enough,
because only the final shape is asked for, and that is O(n * depth).
Better still, carry the height on each root:
height[i] = 0 for every i
in join, when ru is attached under rv:
height[rv] = max(height[rv], height[ru] + 1)
answer = max over roots r of height[r]
## Why carrying the height is correct
height[r] is claimed to be the longest chain below the root r. Attaching ru under
rv lengthens every chain in ru's tree by exactly one and leaves rv's tree alone, so
the longest chain under rv afterwards is the larger of what it was and height[ru] + 1.
No other tree changes at all, and the entry for ru is never read again because ru is no
longer a root.
## Why the limits here are small
n and q are capped at 2000 rather than the 200000 used elsewhere in this topic, because
the structure being simulated really is slow: a single root call can walk n - 1
pointers. That cap is the point of the problem rather than a concession.
## The two joins that change nothing
u equal to v finds the same root twice and must not touch any pointer. A pair that has
already been joined likewise. Writing parent[ru] = rv without the ru != rv test turns a
root into its own parent's parent and can build a loop, after which root never terminates.
## Cross-reference
Problem 997 measures the SAME structure with both optimisations switched on, and counts pointer steps rather than depth, so the two numbers are directly comparable in spirit.
## Cost
Time O(n + q * depth), which is O(n q) in the worst case and is exactly what the problem
is about. Space O(n).
Constraints - `1 ≤ n ≤ 2000` - `0 ≤ q ≤ 2000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, and a pair may repeat.
Input
The first line contains two integers n and q.
Each of the next q lines contains two integers u and v, one join in the order given.
Output
Print one integer: the largest number of pointer steps from any element to its root once every join has been done. Print it alone on one line, with no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.