Skip to content

🕸️ Напреднали Графови Алгоритми

Тези алгоритми се базират на DFS и се използват за анализ на свързаността и структурата на графа. Те представляват едни от най-елегантните и мощни техники в състезателното програмиране, позволявайки решаване на сложни проблеми за графова свързаност, цикли и структурни свойства.

Ключова концепция при повечето от тези алгоритми е използването на DFS дърво и "low-link" стойности, които ни позволяват да открием критични елементи в графа - такива, чието премахване променя структурата или свързаността на графа.

1. Мостове и Артикулационни Точки (Bridges & AP)

В ненасочен граф: * Мост: Ребро, чието премахване увеличава броя на свързаните компоненти. Мостовете са критични връзки в мрежа - без тях графът се разпада. * Артикулационна точка (Cut Vertex): Връх, чието премахване увеличава броя на свързаните компоненти. Това са критичните възли в мрежата.

1.1. Алгоритъм на Тарян (DFS Tree)

Алгоритъмът използва две важни понятия: - tin[u] - време на влизане във връх \(u\) при DFS обхождането - low[u] - най-малкото tin, достижимо от \(u\) чрез поддървото му и максимум едно обратно ребро

Основна идея: Ребро \((u, v)\) е мост ако от поддървото на \(v\) не можем да стигнем до предшественик на \(u\) през обратни ребра.

  1. Започваме DFS от произволен връх (обикновено корена).
  2. За всяко дете \(v\) на \(u\):
    • Ако \(v\) е родител на \(u\), пропускаме (избягваме да се връщаме назад).
    • Ако \(v\) е вече посетен (обратно ребро): low[u] = min(low[u], tin[v]). Обратното ребро ни позволява да стигнем до по-висок предшественик.
    • Ако \(v\) не е посетен (ребро на DFS дървото):
      • Извикваме рекурсивно dfs(v)
      • Обновяваме: low[u] = min(low[u], low[v])
      • Условие за мост: Ако low[v] > tin[u], то \((u, v)\) е Мост (от \(v\) не можем да стигнем до или над \(u\))
      • Условие за артикулационна точка: Ако low[v] >= tin[u], то \(u\) е Артикулационна точка

Специален случай за корена: Коренът на DFS дървото е артикулационна точка само ако има поне 2 деца в DFS дървото.

1.2. Имплементация за намиране на мостове

vector<int> adj[MAXN];
bool visited[MAXN];
int tin[MAXN], low[MAXN];
int timer = 0;
vector<pair<int, int>> bridges;

void dfs(int u, int parent = -1) {
    visited[u] = true;
    tin[u] = low[u] = timer++;

    for (int v : adj[u]) {
        if (v == parent) continue;  // Избягваме връщане назад

        if (visited[v]) {
            // Обратно ребро - обновяваме low
            low[u] = min(low[u], tin[v]);
        } else {
            // Ребро на DFS дървото
            dfs(v, u);
            low[u] = min(low[u], low[v]);

            // Проверка за мост
            if (low[v] > tin[u]) {
                bridges.push_back({u, v});
            }
        }
    }
}

void findBridges(int n) {
    timer = 0;
    bridges.clear();
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }
}

1.3. Имплементация за намиране на артикулационни точки

vector<int> adj[MAXN];
bool visited[MAXN];
int tin[MAXN], low[MAXN];
int timer = 0;
set<int> articulation_points;

void dfs(int u, int parent = -1) {
    visited[u] = true;
    tin[u] = low[u] = timer++;
    int children = 0;  // Брой деца в DFS дървото

    for (int v : adj[u]) {
        if (v == parent) continue;

        if (visited[v]) {
            low[u] = min(low[u], tin[v]);
        } else {
            dfs(v, u);
            low[u] = min(low[u], low[v]);

            // Проверка за артикулационна точка
            if (low[v] >= tin[u] && parent != -1) {
                articulation_points.insert(u);
            }
            children++;
        }
    }

    // Специален случай: коренът е AP ако има >= 2 деца
    if (parent == -1 && children > 1) {
        articulation_points.insert(u);
    }
}

void findArticulationPoints(int n) {
    timer = 0;
    articulation_points.clear();
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }
}

1.4. Приложения

  • Анализ на мрежи: Откриване на критични връзки в комуникационни мрежи
  • Планиране на инфраструктура: Идентифициране на критични точки при проектиране
  • Оптимизация на мрежи: Определяне кои връзки/възли трябва да се подсилят

2. Силно Свързани Компоненти (SCC)

В насочен граф, SCC (Strongly Connected Component) е максимално подмножество от върхове, където всеки връх е достижим от всеки друг връх в това подмножество. С други думи, за всеки два върха \(u\) и \(v\) в един SCC, съществува път от \(u\) до \(v\) И път от \(v\) до \(u\).

Важно свойство: Кондензацията на графа (свиването на всеки SCC в един супер-връх) винаги дава DAG (Directed Acyclic Graph). Това свойство е изключително полезно за решаване на много задачи.

2.1. Алгоритъм на Косарайю (Kosaraju's Algorithm)

Този алгоритъм е по-интуитивен и използва два DFS обхождания:

vector<int> adj[MAXN], adj_rev[MAXN];  // Граф и обърнат граф
bool visited[MAXN];
vector<int> order;  // Ред на приключване
int comp[MAXN];     // Номер на компонента за всеки връх

void dfs1(int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) dfs1(v);
    }
    order.push_back(u);  // Добавяме при завършване
}

void dfs2(int u, int component) {
    comp[u] = component;
    for (int v : adj_rev[u]) {
        if (comp[v] == -1) dfs2(v, component);
    }
}

void findSCC_Kosaraju(int n) {
    // Стъпка 1: Първи DFS за намиране на реда на приключване
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) dfs1(i);
    }

    // Стъпка 2: DFS на обърнатия граф в обратен ред
    fill(comp, comp + n + 1, -1);
    int num_components = 0;
    reverse(order.begin(), order.end());

    for (int u : order) {
        if (comp[u] == -1) {
            dfs2(u, num_components++);
        }
    }
}

2.2. Алгоритъм на Тарян за SCC

Използва едно DFS обхождане и стек. По-ефективен от Косарайю:

vector<int> adj[MAXN];
int tin[MAXN], low[MAXN], timer = 0;
bool on_stack[MAXN];
stack<int> st;
int comp[MAXN], num_components = 0;

void dfs(int u) {
    tin[u] = low[u] = timer++;
    st.push(u);
    on_stack[u] = true;

    for (int v : adj[u]) {
        if (tin[v] == -1) {
            // v не е посетен
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (on_stack[v]) {
            // v е в текущия SCC
            low[u] = min(low[u], tin[v]);
        }
    }

    // Ако u е коренът на SCC
    if (low[u] == tin[u]) {
        while (true) {
            int v = st.top();
            st.pop();
            on_stack[v] = false;
            comp[v] = num_components;
            if (v == u) break;
        }
        num_components++;
    }
}

void findSCC_Tarjan(int n) {
    fill(tin, tin + n + 1, -1);
    fill(on_stack, on_stack + n + 1, false);
    num_components = 0;

    for (int i = 1; i <= n; i++) {
        if (tin[i] == -1) {
            dfs(i);
        }
    }
}

2.3. Приложения на SCC

  1. Намиране на цикли в насочени графи: Ако SCC съдържа > 1 връх, има цикъл
  2. Построяване на кондензационен граф: Полезно за DP на DAG
  3. Проверка за силна свързаност: Графът е силно свързан ⟺ има точно един SCC
  4. 2-SAT: (виж по-долу)

3. 2-SAT (2-Satisfiability)

Имаме набор от булеви променливи \(x_1, \ldots, x_n\) и условия от вида \((a \lor b)\), където \(a\) и \(b\) са литерали (\(x_i\) или \(\neg x_i\)). Искаме да намерим стойности (True/False), удовлетворяващи всички условия, или да определим че такива не съществуват.

Проблемът: Това е NP-пълен проблем за общия SAT, но когато всяко условие има точно 2 литерала (2-SAT), той може да се реши за полиномиално време!

3.1. Свеждане до SCC

Условието \((a \lor b)\) е еквивалентно на две импликации: - \((\neg a \Rightarrow b)\) - "ако \(a\) е False, то \(b\) трябва да е True" - \((\neg b \Rightarrow a)\) - "ако \(b\) е False, то \(a\) трябва да е True"

Алгоритъм: 1. Строим граф на импликациите с \(2n\) върха - по един за \(x_i\) и \(\neg x_i\) за всяка променлива. 2. За всяко условие \((a \lor b)\) добавяме ребра \(\neg a \to b\) и \(\neg b \to a\). 3. Намираме SCC на графа. 4. Проверка за решение: Ако някоя променлива \(x_i\) и \(\neg x_i\) са в един и същи SCC → Няма решение (противоречие). 5. Намиране на решение: В топологичния ред на кондензационния граф, ако \(SCC(x_i)\) е след \(SCC(\neg x_i)\), избираме \(x_i = True\), иначе \(x_i = False\).

3.2. Имплементация

vector<int> adj[2 * MAXN];  // 2n върха: i и i+n за x_i и neg(x_i)
int comp[2 * MAXN];
int n;  // Брой променливи

// Помощна функция: връща индекс на литерала
// i -> x_i (i >= 1), -i -> neg(x_i)
int getNode(int literal) {
    if (literal > 0) return literal;
    return n + (-literal);
}

// Добавяне на клауза (a OR b)
void addClause(int a, int b) {
    // (a OR b) == (NOT a => b) AND (NOT b => a)
    adj[getNode(-a)].push_back(getNode(b));
    adj[getNode(-b)].push_back(getNode(a));
}

bool solve2SAT() {
    // Намираме SCC (с Тарян или Косарайю)
    findSCC_Tarjan(2 * n);

    // Проверяваме за противоречия
    for (int i = 1; i <= n; i++) {
        if (comp[i] == comp[n + i]) {
            return false;  // x_i и neg(x_i) в един SCC - няма решение
        }
    }

    // Има решение - можем да го конструираме
    return true;
}

// Конструиране на конкретно решение
vector<bool> getAssignment() {
    vector<bool> result(n + 1);
    for (int i = 1; i <= n; i++) {
        // Ако SCC на x_i е по-късно в топологичния ред (по-малък номер)
        result[i] = (comp[i] > comp[n + i]);
    }
    return result;
}

3.3. Пример: Задача Giant Pizza

Имаме \(n\) клиента и \(m\) топинга. Всеки клиент иска или не иска точно 2 топинга. Трябва да решим дали можем да направим пица, която да удовлетвори всички:

void solvePizza(int n, int m, vector<array<int, 4>>& customers) {
    // customers[i] = {topping1, want1, topping2, want2}
    // want = 1 ако иска, -1 ако не иска

    for (auto [t1, w1, t2, w2] : customers) {
        int a = (w1 == 1) ? t1 : -t1;  // Литерал за първи топинг
        int b = (w2 == 1) ? t2 : -t2;  // Литерал за втори топинг
        addClause(a, b);  // Добавяме (a OR b)
    }

    if (solve2SAT()) {
        vector<bool> assignment = getAssignment();
        for (int i = 1; i <= m; i++) {
            cout << (assignment[i] ? '+' : '-') << " ";
        }
    } else {
        cout << "IMPOSSIBLE\n";
    }
}

3.4. Практически съвети за 2-SAT

  • Внимавайте с индексацията: често се бъркат \(x_i\) и \(\neg x_i\)
  • Проверете дали графът е правилно построен - дебъгвайте с малки примери
  • При построяване на решението, топологичният ред на SCC е важен
  • 2-SAT е често срещан в задачи с двоичен избор и ограничения

4. Допълнителни приложения и техники

4.1. Bi-connected компоненти

Два върха са в една bi-connected компонента ако има поне два вървопро-независими пътя между тях. Можем да ги намерим използвайки артикулационни точки.

4.2. Edge-based свързаност

Понякога искаме да разгледаме графа от гледна точка на ребрата - например да намерим минималния брой ребра, които трябва да премахнем за да направим графа несвързан.

4.3. Кондензационен граф

След намиране на SCC, можем да построим кондензационен граф където всеки SCC е свит в един връх. Този граф винаги е DAG и можем да прилагаме техники за DAG (топологично сортиране, DP и др.).

vector<int> condensation[MAXN];

void buildCondensation(int n, int num_scc) {
    set<pair<int,int>> edges_added;  // Избягваме дублиране на ребра

    for (int u = 1; u <= n; u++) {
        for (int v : adj[u]) {
            if (comp[u] != comp[v]) {
                if (edges_added.find({comp[u], comp[v]}) == edges_added.end()) {
                    condensation[comp[u]].push_back(comp[v]);
                    edges_added.insert({comp[u], comp[v]});
                }
            }
        }
    }
}

5. Задачи за упражнение

Основни задачи

  1. SPOJ EC_P: Critical Edges (Bridges) - основна задача за мостове.
  2. SPOJ SUBMERGE: Submerging Islands (Articulation Points) - класическа задача за AP.
  3. CSES Planets and Kingdoms: Намиране на SCC - отлична за начало.

Средни задачи

  1. CSES Giant Pizza: 2-SAT задача - много добре формулирана.
  2. Codeforces 427C: Checkposts (SCC) - комбинация от SCC и комбинаторика.
  3. CSES Flight Routes Check: Проверка дали графът е силно свързан.

Напреднали задачи

  1. Codeforces 652D: Nested Segments - нестандартно приложение на SCC.
  2. SPOJ TOUR: Намиране на Ейлеров цикъл с SCC.
  3. Codeforces 292E: Copying Data - сегментни дървета и SCC.

6. Типични грешки и debug съвети

6.1. Често срещани грешки

  1. Забравяне на проверката parent != -1 при артикулационни точки
  2. Грешна инициализация на low и tin стойностите
  3. Объркване на индексите при 2-SAT (\(x_i\) vs \(\neg x_i\))
  4. Забравяне на мултиребра при намиране на мостове
  5. Неправилен ред на обхождане при Косарайю

6.2. Debug съвети

  • Тествайте с малки примери (3-5 върха)
  • Визуализирайте графа и DFS дървото
  • Принтирайте tin и low стойности за всеки връх
  • Проверете дали правилно обработвате специалните случаи (корен на DFS)
  • При 2-SAT, проверете дали импликационният граф е правилно построен

🏁 Заключение

Напредналите графови алгоритми са мощни инструменти за анализ на структурата и свързаността на графи. Ключът към тяхното разбиране е концепцията за low-link стойности и DFS дървото.

Основни takeaways: - Мостове и AP: Критични елементи в мрежата - научете да ги намирате за \(O(V + E)\) - SCC: Свиване на циклите в DAG - позволява DP и топологично сортиране - 2-SAT: Елегантно свеждане на булев проблем до графов - използва SCC

Тези алгоритми често се комбинират с други техники (DP, жадни алгоритми, binary search) за решаване на сложни състезателни задачи. Практикувайте ги докато не ви станат интуитивни - те са сред най-красивите и полезни алгоритми в графовата теория!