Блог

Вам предоставляется неориентированный связный граф с n узлами и n ребрами. Теперь заданы два узла a и b. найдите количество ребер, которые лежат на пути от a до b, но не являются частью цикла. (поскольку количество ребер равно n, цикл наверняка будет). Может ли это быть сделано с помощью структуры данных dsu, потому что, если удаление ребра разъединяет a и b, мы можем посчитать это в ответ. Заранее спасибо.

Конечно, вы можете решить проблему с помощью DSU, как вы упомянули, но это решение недостаточно эффективно. DSU плохо справляется с удалением ребер, поэтому, если вы хотите использовать DSU для решения проблемы, вам необходимо

 for e in E
   use E-e to construct a DSU
   check the connectivity of a and b
  

Даже если вы реализуете DSU с помощью метода сжатия пути и слияния по рангу, временная сложность для одного запроса равна O(n ^2a(n)), где a(n) — функция антиакерманна. Это неприемлемо.

Если вы действительно хотите решить проблему путем перечисления и удаления ребер, рекомендуется связать вырезанное дерево, которое может удалить или добавить ребро за O (logn) времени. Таким образом, вы можете ответить на запрос за O (nlogn) времени.

Но существуют некоторые действительно эффективные алгоритмы, которые могут ответить на каждый запрос за O (1) раз, если вы выполните некоторую предварительную обработку. Граф особенный: связный граф с n вершинами и n ребрами имеет только один цикл. Мы можем рассматривать этот граф как цикл с t вершинами, каждая вершина является корнем дерева. Итак, во время предварительной обработки мы используем dfs для вычисления того, в каком дереве находится каждая вершина, и глубины каждой вершины (в соответствующем дереве глубина каждого корня равна 0). Кроме того, мы используем алгоритм Тарьяна для предварительной обработки каждого дерева с целью запроса LCA за O (1) раз.

Затем для каждого запроса, учитывая две вершины u и v , мы сначала проверяем, находятся ли они в одном дереве. Возможны две ситуации:

• Если ответ положительный, кратчайший путь между ними полностью находится внутри дерева, поэтому нам нужно только вычислить расстояние между u и v , и, очевидно, кратчайшее расстояние равно глубине (u) глубина (v) -2 * глубина (LCA).
• Если ответ отрицательный, путь между u и v можно разделить на 3 части: первая часть находится в дереве (u), вторая часть находится в цикле, а третья часть находится в дереве (v). В этом случае количество ребер внутри деревьев равно просто глубине (u) depth(v).

Применяя описанный выше алгоритм, мы можем решить проблему с помощью предварительной обработки O (n) временной сложности, а затем O (1) временной сложности для каждого запроса. Если есть q запросы и q они довольно большие, этот алгоритм покажет свое преимущество.