Топологическая сортировка: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 1: Строка 1:
* Порядок топологической сортировки — порядок убывания времени выхода из вершины.
* Каждую вершину при выходе из DFS кладём в контейнер, который после переворачиваем (также можно использовать стек).
vector<int> g[V_CNT];
bool u[V_CNT];
vector<int> order;
void dfs(int v) {
    u[v] = 1;
    for (int i = 0; i < g[v].size(); i++)
        if (!u[g[v][i]])
            dfs(g[v][i]);
    order.push_back(v);
}
for (int i = 0; i < V_CNT; i++)
    u[i] = 0;
for (int i = 0; i < V_CNT; i++)
    if (!u[i])
        dfs(i);
reverse(order.begin(), order.end());
== Ссылки на задачи ==
== Ссылки на задачи ==
* [http://acm.timus.ru/problem.aspx?space=1&num=1022 Timus #1022 &mdash; Генеалогическое дерево]
* [http://acm.timus.ru/problem.aspx?space=1&num=1022 Timus #1022 &mdash; Генеалогическое дерево]

Версия от 19:14, 1 октября 2014

  • Порядок топологической сортировки — порядок убывания времени выхода из вершины.
  • Каждую вершину при выходе из DFS кладём в контейнер, который после переворачиваем (также можно использовать стек).
vector<int> g[V_CNT];
bool u[V_CNT];
vector<int> order;

void dfs(int v) {
    u[v] = 1;
    for (int i = 0; i < g[v].size(); i++)
        if (!u[g[v][i]])
            dfs(g[v][i]);
    order.push_back(v);
}

for (int i = 0; i < V_CNT; i++)
    u[i] = 0;
for (int i = 0; i < V_CNT; i++)
    if (!u[i])
        dfs(i);
reverse(order.begin(), order.end());

Ссылки на задачи

Ссылки

Источник — https://acm.khpnets.info/w39/index.php?title=Топологическая_сортировка&oldid=995