Grade 11 · Directed graphs and shortest pathsCitește în română

Topological sort

Original: Sortarea topologică

O(n²)C++1787 lines2 examples

The idea

The arc (x, y) means 'x must be done before y'. A topological sort is an order of all nodes in which every arc goes from left to right; it exists only if the graph has no cycles. We compute the in-degrees. At every step we choose an unused node with in-degree 0 (here the one with the smallest number, so the order is unique), write it and 'delete' the arcs leaving it, decreasing the in-degrees of its neighbours. If at some point no node with in-degree 0 is left, the graph has a cycle.

Original description (Romanian)

Arcul (x, y) înseamnă „x trebuie făcut înaintea lui y”. O sortare topologică este o ordine a tuturor nodurilor în care fiecare arc merge de la stânga la dreapta; ea există doar dacă graful nu are circuite. Calculăm gradele interne. La fiecare pas alegem un nod nefolosit cu grad intern 0 (aici pe cel cu numărul cel mai mic, ca ordinea să fie unică), îl scriem și „ștergem” arcele care pleacă din el, scăzând gradele interne ale vecinilor. Dacă la un moment dat nu mai există niciun nod cu grad intern 0, graful are un circuit.

Complexity
O(n² + m) in this version
Grade
Grade 11 (Clasa a XI-a)

Examples

Example 1

Input

6 6
6 3
6 1
5 1
5 2
3 4
4 2

Expected output

5 6 1 3 4 2
Example 2

Input

3 3
1 2
2 3
3 1

Expected output

Graful are circuit

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

sortare-topologica.cpp
/*
 * Titlu: Sortarea topologică
 * Clasa: 11
 * Capitol: Grafuri orientate și drumuri minime
 * Descriere: Arcul (x, y) înseamnă „x trebuie făcut înaintea lui y”. O sortare topologică
 *            este o ordine a tuturor nodurilor în care fiecare arc merge de la stânga la
 *            dreapta; ea există doar dacă graful nu are circuite. Calculăm gradele interne.
 *            La fiecare pas alegem un nod nefolosit cu grad intern 0 (aici pe cel cu numărul
 *            cel mai mic, ca ordinea să fie unică), îl scriem și „ștergem” arcele care pleacă
 *            din el, scăzând gradele interne ale vecinilor. Dacă la un moment dat nu mai
 *            există niciun nod cu grad intern 0, graful are un circuit.
 * Complexitate: O(n² + m) în această variantă
 *
 * Exemplu
 * Intrare:
 * 6 6
 * 6 3
 * 6 1
 * 5 1
 * 5 2
 * 3 4
 * 4 2
 * Ieșire: 5 6 1 3 4 2
 *
 * Exemplu
 * Intrare:
 * 3 3
 * 1 2
 * 2 3
 * 3 1
 * Ieșire: Graful are circuit
 */
#include <iostream>
using namespace std;

int a[105][105], gradIntern[105], ordine[105];
bool folosit[105];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int k = 1; k <= m; k++)
    {
        int x, y;
        cin >> x >> y;
        if (a[x][y] == 0)
        {
            a[x][y] = 1;
            gradIntern[y]++;
        }
    }

    for (int pas = 1; pas <= n; pas++)
    {
        int x = 0;
        for (int i = 1; i <= n && x == 0; i++)
        {
            if (!folosit[i] && gradIntern[i] == 0)
            {
                x = i;
            }
        }
        if (x == 0)
        {
            cout << "Graful are circuit\n";
            return 0;
        }
        folosit[x] = true;
        ordine[pas] = x;
        for (int y = 1; y <= n; y++)
        {
            if (a[x][y] == 1)
            {
                gradIntern[y]--;
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        cout << ordine[i] << ' ';
    }
    cout << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.