Задача "Эх, дороги..."

Храним каждую компоненту связности (цепь или цикл) в виде отдельного декартова дерева. Тогда чтобы найти кратчайший путь между двумя какими-то вершинами, надо просто найти, какие они по счёту в их декартовом дереве (т.е. найти, сколько элементов стояло до них). Если компонента - путь, то ответом будет просто модуль разности между найденными величинами, а если цикл - то минимум из этого модуля и длины цикла минус этот модуль.

Для этого достаточно для каждой вершины хранить указатель на её структуру в декартовом дереве, и ещё в каждой вершине деревьев поддерживать указатель на вершину-предка.

Тогда, чтобы определить, в каком дереве вершина и какая по счёту, надо просто идти от выбранной вершины по предкам до корня. Корень и будет уникальным идентификатором декартова дерева, по корням мы можем определять, находятся две вершины в одной компоненте связности или нет.

Теперь осталось определить номер вершины. Но здесь всё просто - вот когда мы поднимались по предкам, - можно заметить, что если мы переходим к предку и являемся его правым сыном, то к ответу надо прибавить количество вершин в левом поддереве этого предка. Ещё вначале надо прибавить число вершин в левом поддереве текущей вершины. В итоге получится число вершин, меньших текущей, что в нашем понимании и есть номер вершины в компоненте связности.