Topological Sort

Топологиялық сортировка деген не?

Топологиялық сортировка — ориентированный графтағы вершина тәртібі. Егер графта a → b ребросы болса, онда a вершинасы b вершинасынан бұрын тұруы керек.

a → b
онда a бұрын, b кейін

Топологиялық сортировка тек cycle жоқ ориентированный графта болады. Мұндай граф DAG деп аталады.

DAG деген не?

DAG — Directed Acyclic Graph.

Яғни:

граф ориентированный
ребролардың бағыты бар
графта cycle жоқ

Directed = бағытталған
Acyclic = цикл жоқ
Graph = граф

Мысал

Мынадай dependency болсын:

1 → 2
1 → 3
2 → 4
3 → 4

Бір дұрыс топологиялық тәртіп:

1 2 3 4

Басқа дұрыс тәртіп:

1 3 2 4

Екеуі де дұрыс, себебі 1 вершинасы 2 және 3-тен бұрын, ал 2 және 3 вершинасы 4-тен бұрын тұр.

Қай жерде қолданылады?

dependency бар задачаларда
істерді дұрыс ретпен орындауда
курс prerequisite задачаларында
файлдарды compile жасау тәртібінде
ориентированный графта cycle бар ма тексеруде
DAG бойынша dynamic programming жасауда

Метод 1: DFS арқылы

Идея:

DFS бастаймыз
алдымен барлық көрші вершинаға кіреміз
кейін ғана қазіргі вершина answer-ға қосылады
соңында answer-ды reverse жасаймыз

Неге reverse керек? Себебі DFS кезінде вершина барлық потомок обработка болғаннан кейін ғана қосылады.

DFS шаблон

void dfs(int v) {
    used[v] = true;

    for (int to : g[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }

    ans.push_back(v);
}

Барлық DFS біткеннен кейін:

reverse(ans.begin(), ans.end());

Задача 1: топологиялық тәртіп табу

Ориентированный ациклический граф берілген. Бір дұрыс топологиялық тәртіп шығару керек.

Input

Output

1 3 2 4

Жауап жалғыз болмауы мүмкін.

DFS арқылы толық реализация

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
vector<int> g[N];
bool used[N];
vector<int> ans;

void dfs(int v) {
    used[v] = true;

    for (int to : g[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }

    ans.push_back(v);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
    }

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

    reverse(ans.begin(), ans.end());

    for (int x : ans) {
        cout << x << ' ';
    }

    return 0;
}

DFS версиясының проблемасы

Обычный DFS версиясы тек тәртіп құрады. Бірақ егер графта cycle болса, топологиялық сортировка жоқ.

cycle бар → topsort жоқ
cycle жоқ → topsort бар

Сондықтан cycle тексеруді де білу керек.

Cycle тексеру: color әдісі

color массивін қолданамыз:

0 — вершинаға әлі кірмедік
1 — қазір DFS ішінде тұр
2 — толық обработка болды

Егер v вершинасынан to вершинасына барғанда color[to] == 1 болса, онда cycle бар.

Cycle тексеретін DFS

bool hasCycle = false;

void dfs(int v) {
    color[v] = 1;

    for (int to : g[v]) {
        if (color[to] == 0) {
            dfs(to);
        } else if (color[to] == 1) {
            hasCycle = true;
        }
    }

    color[v] = 2;
    ans.push_back(v);
}

Cycle тексерумен толық код

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
vector<int> g[N];
int color[N];
vector<int> ans;
bool hasCycle = false;

void dfs(int v) {
    color[v] = 1;

    for (int to : g[v]) {
        if (color[to] == 0) {
            dfs(to);
        } else if (color[to] == 1) {
            hasCycle = true;
        }
    }

    color[v] = 2;
    ans.push_back(v);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
    }

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

    if (hasCycle) {
        cout << -1;
        return 0;
    }

    reverse(ans.begin(), ans.end());

    for (int x : ans) {
        cout << x << ' ';
    }

    return 0;
}

Метод 2: Kahn алгоритмі

Екінші әдіс — кіретін ребролар саны арқылы. Бұл Kahn algorithm деп аталады.

indeg[v] — v вершинасына қанша ребро кіріп тұрғанын көрсетеді.

indeg[v]

Егер indeg[v] == 0, онда бұл вершинаға дейін dependency жоқ. Оны answer-ға қосуға болады.

Kahn алгоритмінің идеясы

барлық вершина үшін indeg санаймыз
indeg = 0 болатын вершина queue-ға салынады
queue-дан вершина аламыз
answer-ға қосамыз
оның көршілерінің indeg мәнін азайтамыз
егер көршінің indeg мәні 0 болса, queue-ға саламыз

Kahn алгоритмі: код идеясы

queue<int> q;

for (int i = 1; i <= n; i++) {
    if (indeg[i] == 0) {
        q.push(i);
    }
}

while (!q.empty()) {
    int v = q.front();
    q.pop();

    ans.push_back(v);

    for (int to : g[v]) {
        indeg[to]--;

        if (indeg[to] == 0) {
            q.push(to);
        }
    }
}

Cycle бар екенін қалай білеміз?

Егер Kahn алгоритмінен кейін answer ішінде барлық вершина болмаса, онда графта cycle бар.

if (ans.size() != n) {
    cout << -1;
}

Себебі cycle ішінде indeg = 0 болатын вершина табылмай қалады.

Kahn алгоритмінің толық коды

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
vector<int> g[N];
int indeg[N];
vector<int> ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        indeg[b]++;
    }

    queue<int> q;

    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        ans.push_back(v);

        for (int to : g[v]) {
            indeg[to]--;

            if (indeg[to] == 0) {
                q.push(to);
            }
        }
    }

    if ((int)ans.size() != n) {
        cout << -1;
        return 0;
    }

    for (int x : ans) {
        cout << x << ' ';
    }

    return 0;
}

Лексикографиялық минималды topsort

Кейде ең кіші топологиялық тәртіп керек болады. Ондай кезде queue орнына priority_queue min-heap ретінде қолданылады.

priority_queue<int, vector<int>, greater<int>> q;

Сонда әр қадамда ең кіші доступный вершина алынады.

Минималды topsort коды

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
vector<int> g[N];
int indeg[N];
vector<int> ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        indeg[b]++;
    }

    priority_queue<int, vector<int>, greater<int>> q;

    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int v = q.top();
        q.pop();

        ans.push_back(v);

        for (int to : g[v]) {
            indeg[to]--;

            if (indeg[to] == 0) {
                q.push(to);
            }
        }
    }

    if ((int)ans.size() != n) {
        cout << -1;
        return 0;
    }

    for (int x : ans) {
        cout << x << ' ';
    }

    return 0;
}

DFS vs Kahn

Метод	Идея	Плюс
DFS	потомоктардан кейін вершина қосылады	код қысқа
Kahn	indeg = 0 вершинасын өшіреміз	cycle және minimal order табуға ыңғайлы

Асимптотика

Метод	Уақыт	Память
DFS	O(n + m)	O(n + m)
Kahn queue арқылы	O(n + m)	O(n + m)
Kahn priority_queue арқылы	O((n + m) log n)	O(n + m)

Қысқа шаблон

queue<int> q;

for (int i = 1; i <= n; i++) {
    if (indeg[i] == 0) {
        q.push(i);
    }
}

while (!q.empty()) {
    int v = q.front();
    q.pop();

    ans.push_back(v);

    for (int to : g[v]) {
        indeg[to]--;

        if (indeg[to] == 0) {
            q.push(to);
        }
    }
}

if ((int)ans.size() != n) {
    cout << -1;
} else {
    for (int x : ans) {
        cout << x << ' ';
    }
}