Пошук мостів онлайн

Нам дано неорієнтований граф. Міст — це таке ребро, видалення якого робить граф незв'язним (точніше, збільшує кількість компонент зв'язності). Наше завдання — знайти всі мости в заданому графі.

Неформально це завдання можна сформулювати так: ми маємо знайти всі «важливі» дороги на заданій карті доріг, тобто такі дороги, видалення будь-якої з яких призведе до того, що деякі міста стануть недосяжними з інших.

Уже існує стаття Пошук мостів за $O(N+M)$, яка розв'язує це завдання за допомогою обходу пошуком у глибину. Цей алгоритм буде значно складнішим, але має одну велику перевагу: описаний у цій статті алгоритм працює онлайн, тобто вхідний граф не обов'язково знати заздалегідь. Ребра додаються по одному за раз, і після кожного додавання алгоритм перераховує всі мости в поточному графі. Іншими словами, алгоритм розроблено так, щоб ефективно працювати на динамічному графі, який змінюється.

Більш строго постановка задачі виглядає так: Спочатку граф порожній і складається з $n$ вершин. Потім ми отримуємо пари вершин $(a, b)$, які позначають ребро, що додається до графа. Після кожного отриманого ребра, тобто після додавання кожного ребра, виводимо поточну кількість мостів у графі.

Також можна підтримувати список усіх мостів, а також явно зберігати компоненти 2-реберної зв'язності.

Описаний нижче алгоритм працює за час $O(n \log n + m)$, де $m$ — кількість ребер. Алгоритм ґрунтується на структурі даних Система неперетинних множин. Однак реалізація в цій статті працює за час $O(n \log n + m \log n)$, оскільки вона використовує спрощену версію СНМ без об'єднання за рангом.

Коли підходить цей алгоритм?

• Граф динамічний — ребра додаються по одному, і кількість мостів треба перераховувати після кожного додавання? (якщо граф статичний і відомий заздалегідь → простіший офлайн Пошук мостів за $O(N+M)$)
• Дозволено лише додавання ребер (без видалень)?
• Потрібно онлайн підтримувати компоненти 2-реберної зв'язності, а не лише лічильник мостів?

Алгоритм

Спершу означимо $k$-реберно зв'язну компоненту: це компонента зв'язності, яка залишається зв'язною, коли ви видаляєте менш ніж $k$ ребер.

Дуже легко бачити, що мости розбивають граф на компоненти 2-реберної зв'язності. Якщо ми стиснемо кожну з цих компонент 2-реберної зв'язності у вершини й залишимо в стисненому графі лише мости як ребра, то отримаємо ациклічний граф, тобто ліс.

Описаний нижче алгоритм явно підтримує цей ліс, а також компоненти 2-реберної зв'язності.

Зрозуміло, що спочатку, коли граф порожній, він містить $n$ компонент 2-реберної зв'язності, які самі по собі не з'єднані.

Під час додавання чергового ребра $(a, b)$ можуть виникнути три ситуації:

• Обидві вершини $a$ і $b$ знаходяться в одній компоненті 2-реберної зв'язності — тоді це ребро не є мостом і нічого не змінює у структурі лісу, тож ми можемо просто пропустити це ребро.

  Отже, у цьому випадку кількість мостів не змінюється.

• Вершини $a$ і $b$ знаходяться в зовсім різних компонентах зв'язності, тобто кожна з них є частиною різного дерева. У цьому випадку ребро $(a, b)$ стає новим мостом, і ці два дерева об'єднуються в одне (а всі старі мости залишаються).

  Отже, у цьому випадку кількість мостів збільшується на одиницю.

• Вершини $a$ і $b$ знаходяться в одній компоненті зв'язності, але в різних компонентах 2-реберної зв'язності. У цьому випадку це ребро утворює цикл разом із деякими зі старих мостів. Усі ці мости перестають бути мостами, і отриманий цикл потрібно стиснути в нову компоненту 2-реберної зв'язності.

  Отже, у цьому випадку кількість мостів зменшується на одиницю або більше.

Відповідно, усе завдання зводиться до ефективної реалізації всіх цих операцій над лісом компонент 2-реберної зв'язності.

Структури даних для зберігання лісу

Єдина структура даних, яка нам потрібна, — це Система неперетинних множин. Насправді ми зробимо дві копії цієї структури: одна слугуватиме для підтримання компонент зв'язності, інша — для підтримання компонент 2-реберної зв'язності. А на додачу ми зберігаємо структуру дерев у лісі компонент 2-реберної зв'язності за допомогою вказівників: кожна компонента 2-реберної зв'язності зберігатиме індекс par[] свого предка в дереві.

Тепер ми послідовно розберемо кожну операцію, яку нам потрібно навчитися реалізовувати:

• Перевірка, чи лежать дві вершини в одній компоненті зв'язності / 2-реберної зв'язності. Це робиться звичайним алгоритмом СНМ, ми просто знаходимо й порівнюємо представників СНМ.

• З'єднання двох дерев для деякого ребра $(a, b)$. Оскільки могло б виявитися, що ні вершина $a$, ні вершина $b$ не є коренями своїх дерев, єдиний спосіб з'єднати ці два дерева — це переробити корінь одного з них. Наприклад, можна зробити коренем дерева вершину $a$, а потім приєднати його до іншого дерева, встановивши предком $a$ вершину $b$.

  Однак виникає питання про ефективність операції зміни кореня: щоб переробити корінь дерева з коренем $r$ на вершину $v$, необхідно відвідати всі вершини на шляху між $v$ і $r$ та перенаправити вказівники par[] у протилежному напрямку, а також змінити посилання на предків у СНМ, що відповідає за компоненти зв'язності.

  Отже, вартість зміни кореня — $O(h)$, де $h$ — висота дерева. Можна зробити навіть гіршу оцінку, сказавши, що вартість становить $O(\text{size})$, де $\text{size}$ — кількість вершин у дереві. Підсумкова складність від цього не зміниться.

  Тепер ми застосовуємо стандартний прийом: робимо новий корінь у тому дереві, яке містить менше вершин. Тоді інтуїтивно зрозуміло, що найгірший випадок — це коли об'єднуються два дерева приблизно однакових розмірів, але тоді результатом є дерево вдвічі більшого розміру. Це не дозволяє такій ситуації траплятися багато разів.

  Загалом сумарну вартість можна записати у вигляді рекурентного співвідношення:

  $$T(n) = \max_{k = 1 \ldots n-1} \left\{ T(k) + T(n - k) + O(\min(k, n - k))\right\}$$

  $T(n)$ — кількість операцій, необхідних, щоб отримати дерево з $n$ вершинами за допомогою зміни кореня та об'єднання дерев. Дерево розміру $n$ можна створити, об'єднавши два менші дерева розмірів $k$ і $n - k$. Це рекурентне співвідношення має розв'язок $T(n) = O (n \log n)$.

  Отже, сумарний час, витрачений на всі операції зміни кореня, буде $O(n \log n)$, якщо ми завжди змінюємо корінь меншого з двох дерев.

  Нам доведеться підтримувати розмір кожної компоненти зв'язності, але структура даних СНМ робить це можливим без труднощів.

• Пошук циклу, утвореного додаванням нового ребра $(a, b)$. Оскільки $a$ і $b$ вже з'єднані в дереві, нам потрібно знайти найнижчого спільного предка вершин $a$ і $b$. Цикл складатиметься зі шляхів від $b$ до LCA, від LCA до $a$ та ребра від $a$ до $b$.

  Після знаходження циклу ми стискаємо всі вершини виявленого циклу в одну вершину. Це означає, що ми вже маємо складність, пропорційну довжині циклу, а отже, ми також можемо використовувати будь-який алгоритм LCA, пропорційний довжині, і не зобов'язані використовувати якийсь швидкий.

  Оскільки вся інформація про структуру дерева доступна в масиві предків par[], єдиний розумний алгоритм LCA такий: позначаємо вершини $a$ і $b$ як відвідані, потім переходимо до їхніх предків par[a] і par[b] та позначаємо їх, потім просуваємося до їхніх предків і так далі, доки не досягнемо вже позначеної вершини. Ця вершина і є LCA, який ми шукаємо, і ми можемо знайти вершини на циклі, знову проходячи шлях від $a$ і $b$ до LCA.

  Очевидно, що складність цього алгоритму пропорційна довжині шуканого циклу.

• Стиснення циклу під час додавання нового ребра $(a, b)$ в дереві.

  Нам потрібно створити нову компоненту 2-реберної зв'язності, яка складатиметься з усіх вершин виявленого циклу (також сам виявлений цикл міг складатися з кількох компонент 2-реберної зв'язності, але це нічого не змінює). Крім того, необхідно стиснути їх так, щоб структура дерева не порушилася, а всі вказівники par[] та дві СНМ залишалися правильними.

  Найпростіший спосіб досягти цього — стиснути всі вершини циклу до їхнього LCA. Насправді LCA є найвищою з вершин, тобто його вказівник на предка par[] залишається незмінним. Для всіх інших вершин циклу предків оновлювати не потрібно, оскільки ці вершини просто перестають існувати. Але в СНМ компонент 2-реберної зв'язності всі ці вершини просто вказуватимуть на LCA.

  Ми реалізуємо СНМ компонент 2-реберної зв'язності без оптимізації об'єднання за рангом, тому отримаємо складність $O(\log n)$ у середньому на запит. Щоб досягти складності $O(1)$ у середньому на запит, нам потрібно об'єднувати вершини циклу згідно з об'єднанням за рангом, а потім відповідно присвоїти par[].

Реалізація

Ось остаточна реалізація всього алгоритму.

Як згадувалося раніше, заради простоти СНМ компонент 2-реберної зв'язності написано без об'єднання за рангом, тому підсумкова складність буде $O(\log n)$ у середньому.

Також у цій реалізації самі мости не зберігаються, лише їхня кількість bridges. Однак буде неважко створити set усіх мостів.

Спочатку ви викликаєте функцію init(), яка ініціалізує дві СНМ (створюючи окрему множину для кожної вершини та встановлюючи розмір рівним одиниці) і задає предків par.

Основна функція — add_edge(a, b), яка обробляє й додає нове ребро.

C++

vector<int> par, dsu_2ecc, dsu_cc, dsu_cc_size;
int bridges;
int lca_iteration;
vector<int> last_visit;
 
void init(int n) {
    par.resize(n);
    dsu_2ecc.resize(n);
    dsu_cc.resize(n);
    dsu_cc_size.resize(n);
    lca_iteration = 0;
    last_visit.assign(n, 0);
    for (int i=0; i<n; ++i) {
        dsu_2ecc[i] = i;
        dsu_cc[i] = i;
        dsu_cc_size[i] = 1;
        par[i] = -1;
    }
    bridges = 0;
}
 
int find_2ecc(int v) {
    if (v == -1)
        return -1;
    return dsu_2ecc[v] == v ? v : dsu_2ecc[v] = find_2ecc(dsu_2ecc[v]);
}
 
int find_cc(int v) {
    v = find_2ecc(v);
    return dsu_cc[v] == v ? v : dsu_cc[v] = find_cc(dsu_cc[v]);
}
 
void make_root(int v) {
    int root = v;
    int child = -1;
    while (v != -1) {
        int p = find_2ecc(par[v]);
        par[v] = child;
        dsu_cc[v] = root;
        child = v;
        v = p;
    }
    dsu_cc_size[root] = dsu_cc_size[child];
}

void merge_path (int a, int b) {
    ++lca_iteration;
    vector<int> path_a, path_b;
    int lca = -1;
    while (lca == -1) {
        if (a != -1) {
            a = find_2ecc(a);
            path_a.push_back(a);
            if (last_visit[a] == lca_iteration){
                lca = a;
                break;
                }
            last_visit[a] = lca_iteration;
            a = par[a];
        }
        if (b != -1) {
            b = find_2ecc(b);
            path_b.push_back(b);
            if (last_visit[b] == lca_iteration){
                lca = b;
                break;
                }
            last_visit[b] = lca_iteration;
            b = par[b];
        }
        
    }

    for (int v : path_a) {
        dsu_2ecc[v] = lca;
        if (v == lca)
            break;
        --bridges;
    }
    for (int v : path_b) {
        dsu_2ecc[v] = lca;
        if (v == lca)
            break;
        --bridges;
    }
}
 
void add_edge(int a, int b) {
    a = find_2ecc(a);
    b = find_2ecc(b);
    if (a == b)
        return;
 
    int ca = find_cc(a);
    int cb = find_cc(b);

    if (ca != cb) {
        ++bridges;
        if (dsu_cc_size[ca] > dsu_cc_size[cb]) {
            swap(a, b);
            swap(ca, cb);
        }
        make_root(a);
        par[a] = dsu_cc[a] = b;
        dsu_cc_size[cb] += dsu_cc_size[a];
    } else {
        merge_path(a, b);
    }
}

Python

import sys
# глибина рекурсії в find_2ecc/find_cc може сягати O(n) для довгого ланцюга,
# тому збільшуємо ліміт; альтернатива — ітеративна версія find (див. нижче)
sys.setrecursionlimit(300000)

par: list[int] = []          # предок компоненти 2-реберної зв'язності в лісі
dsu_2ecc: list[int] = []     # СНМ компонент 2-реберної зв'язності
dsu_cc: list[int] = []       # СНМ компонент зв'язності (лідер = корінь дерева)
dsu_cc_size: list[int] = []  # розміри компонент зв'язності
bridges = 0
lca_iteration = 0            # унікальний ідентифікатор поточного пошуку LCA
last_visit: list[int] = []   # позначка останнього відвідування вершини


def init(n: int) -> None:
    global par, dsu_2ecc, dsu_cc, dsu_cc_size, bridges, lca_iteration, last_visit
    par = [-1] * n
    dsu_2ecc = list(range(n))   # кожна вершина — окрема множина
    dsu_cc = list(range(n))
    dsu_cc_size = [1] * n
    lca_iteration = 0
    last_visit = [0] * n
    bridges = 0


def find_2ecc(v: int) -> int:
    if v == -1:
        return -1
    # ітеративний find зі стисненням шляху (без рекурсії)
    root = v
    while dsu_2ecc[root] != root:
        root = dsu_2ecc[root]
    while dsu_2ecc[v] != root:
        dsu_2ecc[v], v = root, dsu_2ecc[v]
    return root


def find_cc(v: int) -> int:
    v = find_2ecc(v)
    root = v
    while dsu_cc[root] != root:
        root = dsu_cc[root]
    while dsu_cc[v] != root:
        dsu_cc[v], v = root, dsu_cc[v]
    return root


def make_root(v: int) -> None:
    # переробляємо корінь дерева на вершину v, розвертаючи вказівники par
    root = v
    child = -1
    while v != -1:
        p = find_2ecc(par[v])
        par[v] = child
        dsu_cc[v] = root
        child = v
        v = p
    dsu_cc_size[root] = dsu_cc_size[child]


def merge_path(a: int, b: int) -> None:
    # шукаємо LCA, піднімаючи a та b паралельно, і стискаємо цикл
    global lca_iteration, bridges
    lca_iteration += 1
    path_a: list[int] = []
    path_b: list[int] = []
    lca = -1
    while lca == -1:
        if a != -1:
            a = find_2ecc(a)
            path_a.append(a)
            if last_visit[a] == lca_iteration:
                lca = a
                break
            last_visit[a] = lca_iteration
            a = par[a]
        if b != -1:
            b = find_2ecc(b)
            path_b.append(b)
            if last_visit[b] == lca_iteration:
                lca = b
                break
            last_visit[b] = lca_iteration
            b = par[b]

    for v in path_a:
        dsu_2ecc[v] = lca
        if v == lca:
            break
        bridges -= 1
    for v in path_b:
        dsu_2ecc[v] = lca
        if v == lca:
            break
        bridges -= 1


def add_edge(a: int, b: int) -> None:
    global bridges
    a = find_2ecc(a)
    b = find_2ecc(b)
    if a == b:
        return

    ca = find_cc(a)
    cb = find_cc(b)

    if ca != cb:
        # різні дерева — нове ребро є мостом
        bridges += 1
        if dsu_cc_size[ca] > dsu_cc_size[cb]:
            a, b = b, a
            ca, cb = cb, ca
        make_root(a)              # меншому дереву переробляємо корінь
        par[a] = dsu_cc[a] = b
        dsu_cc_size[cb] += dsu_cc_size[a]
    else:
        # одне дерево, різні компоненти 2-реберної зв'язності — стискаємо цикл
        merge_path(a, b)

TypeScript

let par: number[] = [];          // предок компоненти 2-реберної зв'язності в лісі
let dsu2ecc: number[] = [];      // СНМ компонент 2-реберної зв'язності
let dsuCc: number[] = [];        // СНМ компонент зв'язності (лідер = корінь дерева)
let dsuCcSize: number[] = [];    // розміри компонент зв'язності
let bridges = 0;
let lcaIteration = 0;            // унікальний ідентифікатор поточного пошуку LCA
let lastVisit: number[] = [];    // позначка останнього відвідування вершини

function init(n: number): void {
    par = new Array(n);
    dsu2ecc = new Array(n);
    dsuCc = new Array(n);
    dsuCcSize = new Array(n);
    lcaIteration = 0;
    lastVisit = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        dsu2ecc[i] = i;          // кожна вершина — окрема множина
        dsuCc[i] = i;
        dsuCcSize[i] = 1;
        par[i] = -1;
    }
    bridges = 0;
}

// ітеративний find зі стисненням шляху (без рекурсії)
function find2ecc(v: number): number {
    if (v === -1) return -1;
    let root = v;
    while (dsu2ecc[root] !== root) root = dsu2ecc[root];
    while (dsu2ecc[v] !== root) {
        const next = dsu2ecc[v];
        dsu2ecc[v] = root;
        v = next;
    }
    return root;
}

function findCc(v: number): number {
    v = find2ecc(v);
    let root = v;
    while (dsuCc[root] !== root) root = dsuCc[root];
    while (dsuCc[v] !== root) {
        const next = dsuCc[v];
        dsuCc[v] = root;
        v = next;
    }
    return root;
}

// переробляємо корінь дерева на вершину v, розвертаючи вказівники par
function makeRoot(v: number): void {
    const root = v;
    let child = -1;
    while (v !== -1) {
        const p = find2ecc(par[v]);
        par[v] = child;
        dsuCc[v] = root;
        child = v;
        v = p;
    }
    dsuCcSize[root] = dsuCcSize[child];
}

// шукаємо LCA, піднімаючи a та b паралельно, і стискаємо цикл
function mergePath(a: number, b: number): void {
    ++lcaIteration;
    const pathA: number[] = [];
    const pathB: number[] = [];
    let lca = -1;
    while (lca === -1) {
        if (a !== -1) {
            a = find2ecc(a);
            pathA.push(a);
            if (lastVisit[a] === lcaIteration) {
                lca = a;
                break;
            }
            lastVisit[a] = lcaIteration;
            a = par[a];
        }
        if (b !== -1) {
            b = find2ecc(b);
            pathB.push(b);
            if (lastVisit[b] === lcaIteration) {
                lca = b;
                break;
            }
            lastVisit[b] = lcaIteration;
            b = par[b];
        }
    }

    for (const v of pathA) {
        dsu2ecc[v] = lca;
        if (v === lca) break;
        --bridges;
    }
    for (const v of pathB) {
        dsu2ecc[v] = lca;
        if (v === lca) break;
        --bridges;
    }
}

function addEdge(a: number, b: number): void {
    a = find2ecc(a);
    b = find2ecc(b);
    if (a === b) return;

    let ca = findCc(a);
    let cb = findCc(b);

    if (ca !== cb) {
        // різні дерева — нове ребро є мостом
        ++bridges;
        if (dsuCcSize[ca] > dsuCcSize[cb]) {
            [a, b] = [b, a];
            [ca, cb] = [cb, ca];
        }
        makeRoot(a);             // меншому дереву переробляємо корінь
        par[a] = dsuCc[a] = b;
        dsuCcSize[cb] += dsuCcSize[a];
    } else {
        // одне дерево, різні компоненти 2-реберної зв'язності — стискаємо цикл
        mergePath(a, b);
    }
}

Go

var par []int         // предок компоненти 2-реберної зв'язності в лісі
var dsu2ecc []int     // СНМ компонент 2-реберної зв'язності
var dsuCc []int       // СНМ компонент зв'язності (лідер = корінь дерева)
var dsuCcSize []int   // розміри компонент зв'язності
var bridges int
var lcaIteration int  // унікальний ідентифікатор поточного пошуку LCA
var lastVisit []int   // позначка останнього відвідування вершини

func initBridges(n int) {
	par = make([]int, n)
	dsu2ecc = make([]int, n)
	dsuCc = make([]int, n)
	dsuCcSize = make([]int, n)
	lcaIteration = 0
	lastVisit = make([]int, n)
	for i := 0; i < n; i++ {
		dsu2ecc[i] = i // кожна вершина — окрема множина
		dsuCc[i] = i
		dsuCcSize[i] = 1
		par[i] = -1
	}
	bridges = 0
}

// ітеративний find зі стисненням шляху (без рекурсії)
func find2ecc(v int) int {
	if v == -1 {
		return -1
	}
	root := v
	for dsu2ecc[root] != root {
		root = dsu2ecc[root]
	}
	for dsu2ecc[v] != root {
		dsu2ecc[v], v = root, dsu2ecc[v]
	}
	return root
}

func findCc(v int) int {
	v = find2ecc(v)
	root := v
	for dsuCc[root] != root {
		root = dsuCc[root]
	}
	for dsuCc[v] != root {
		dsuCc[v], v = root, dsuCc[v]
	}
	return root
}

// переробляємо корінь дерева на вершину v, розвертаючи вказівники par
func makeRoot(v int) {
	root := v
	child := -1
	for v != -1 {
		p := find2ecc(par[v])
		par[v] = child
		dsuCc[v] = root
		child = v
		v = p
	}
	dsuCcSize[root] = dsuCcSize[child]
}

// шукаємо LCA, піднімаючи a та b паралельно, і стискаємо цикл
func mergePath(a, b int) {
	lcaIteration++
	var pathA, pathB []int
	lca := -1
	for lca == -1 {
		if a != -1 {
			a = find2ecc(a)
			pathA = append(pathA, a)
			if lastVisit[a] == lcaIteration {
				lca = a
				break
			}
			lastVisit[a] = lcaIteration
			a = par[a]
		}
		if b != -1 {
			b = find2ecc(b)
			pathB = append(pathB, b)
			if lastVisit[b] == lcaIteration {
				lca = b
				break
			}
			lastVisit[b] = lcaIteration
			b = par[b]
		}
	}

	for _, v := range pathA {
		dsu2ecc[v] = lca
		if v == lca {
			break
		}
		bridges--
	}
	for _, v := range pathB {
		dsu2ecc[v] = lca
		if v == lca {
			break
		}
		bridges--
	}
}

func addEdge(a, b int) {
	a = find2ecc(a)
	b = find2ecc(b)
	if a == b {
		return
	}

	ca := findCc(a)
	cb := findCc(b)

	if ca != cb {
		// різні дерева — нове ребро є мостом
		bridges++
		if dsuCcSize[ca] > dsuCcSize[cb] {
			a, b = b, a
			ca, cb = cb, ca
		}
		makeRoot(a) // меншому дереву переробляємо корінь
		par[a] = b
		dsuCc[a] = b
		dsuCcSize[cb] += dsuCcSize[a]
	} else {
		// одне дерево, різні компоненти 2-реберної зв'язності — стискаємо цикл
		mergePath(a, b)
	}
}

СНМ для компонент 2-реберної зв'язності зберігається у векторі dsu_2ecc, а функція, що повертає представника, — find_2ecc(v). Ця функція використовується багато разів у решті коду, оскільки після стиснення кількох вершин в одну всі ці вершини перестають існувати, і натомість лише лідер має правильного предка par у лісі компонент 2-реберної зв'язності.

СНМ для компонент зв'язності зберігається у векторі dsu_cc, а також є додатковий вектор dsu_cc_size для зберігання розмірів компонент. Функція find_cc(v) повертає лідера компоненти зв'язності (який насправді є коренем дерева).

Зміна кореня дерева make_root(v) працює так, як описано вище: вона проходить від вершини $v$ через предків до кореневої вершини, щоразу перенаправляючи предка par у протилежному напрямку. Посилання на представника компоненти зв'язності dsu_cc також оновлюється, щоб воно вказувало на нову кореневу вершину. Після зміни кореня ми маємо присвоїти новому кореню правильний розмір компоненти зв'язності. Також нам треба бути уважними й викликати find_2ecc(), щоб отримати представників компоненти 2-реберної зв'язності, а не якусь іншу вершину, яку вже стиснуто.

Функція пошуку й стиснення циклу merge_path(a, b) також реалізована так, як описано вище. Вона шукає LCA вершин $a$ і $b$, піднімаючи ці вузли паралельно, доки не зустрінемо вершину вдруге. З міркувань ефективності ми обираємо унікальний ідентифікатор для кожного виклику пошуку LCA й позначаємо ним пройдені вершини. Це працює за $O(1)$, тоді як інші підходи, як-от використання $set$, працюють гірше. Пройдені шляхи зберігаються у векторах path_a і path_b, і ми використовуємо їх, щоб пройтися ними вдруге до LCA, отримавши таким чином усі вершини циклу. Усі вершини циклу стискаються приєднанням до LCA, тому середня складність — $O(\log n)$ (оскільки ми не використовуємо об'єднання за рангом). Усі ребра, які ми проходимо, були мостами, тому ми віднімаємо 1 за кожне ребро в циклі.

Нарешті, функція-запит add_edge(a, b) визначає компоненти зв'язності, у яких лежать вершини $a$ і $b$. Якщо вони лежать у різних компонентах зв'язності, то менше дерево змінює корінь, а потім приєднується до більшого дерева. Інакше, якщо вершини $a$ і $b$ лежать в одному дереві, але в різних компонентах 2-реберної зв'язності, то викликається функція merge_path(a, b), яка виявить цикл і стисне його в одну компоненту 2-реберної зв'язності.