uniolympiads English

Τοπολογική ταξινόμηση

Σειρά των κορυφών ενός DAG ώστε κάθε ακμή να πηγαίνει προς τα εμπρός, σε O(n+m)O(n + m). Πάνω της τρέχει κάθε DP σε DAG.

Πότε

Εξαρτήσεις («το μάθημα aa πριν από το bb»), ή DP σε κατευθυνόμενο γράφο χωρίς κύκλους: μακρύτερη διαδρομή, πλήθος διαδρομών, κάτι που υπολογίζεται από τους προκατόχους.

Η ιδέα (Kahn)

Μια κορυφή χωρίς εισερχόμενες ακμές μπορεί να μπει πρώτη. Τη βάζεις, σβήνεις τις ακμές της, και κάποιες άλλες κορυφές μένουν χωρίς εισερχόμενες. Κρατάς τον βαθμό εισόδου κάθε κορυφής και μια ουρά με όσες έχουν βαθμό 0.

Αν στο τέλος έχουν βγει λιγότερες από nn κορυφές, οι υπόλοιπες έχουν πάντα κάποια εισερχόμενη ακμή μεταξύ τους. Άρα υπάρχει κύκλος, και η συνάρτηση επιστρέφει κενό.

DP σε DAG

Στο Longest Flight Route υπολογίζεις τη μακρύτερη διαδρομή από το 11 στο nn. Διατρέχεις τις κορυφές με την τοπολογική σειρά, οπότε όταν φτάνεις στο vv έχουν ήδη τελειώσει όλοι οι προκάτοχοί του:

f(v)=1+max⁡u→vf(u).f(v) = 1 + \max_{u \to v} f(u).

Στο Game Routes το ίδιο με άθροισμα αντί για μέγιστο, modulo 109+710^9 + 7.

Παγίδες

  • Η τοπολογική σειρά δεν είναι μοναδική. Αν το πρόβλημα θέλει τη λεξικογραφικά μικρότερη, αντικατέστησε την ουρά με priority_queue (ελάχιστο πρώτο).
  • Στο Longest Flight Route κορυφές που δεν είναι προσβάσιμες από το 11 δεν πρέπει να δίνουν τιμή. Ξεκίνα με f=−∞f = -\infty παντού εκτός από το f(1)=1f(1) = 1.

Κώδικας

Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.

cpp/topological-sort.cpp
// Topological order of a directed graph (Kahn's algorithm). O(n + m).
// Returns an empty vector if the graph has a cycle.

vector<int> topologicalSort(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> indeg(n, 0);
    for (int u = 0; u < n; u++) {
        for (int v : adj[u]) {
            indeg[v]++;
        }
    }
    queue<int> q;
    for (int u = 0; u < n; u++) {
        if (indeg[u] == 0) {
            q.push(u);
        }
    }
    vector<int> order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            indeg[v]--;
            if (indeg[v] == 0) {
                q.push(v);
            }
        }
    }
    if ((int)order.size() < n) {
        return {};
    }
    return order;
}

Ελέγχθηκε σε 2.000 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Για εξάσκηση στο CSES

Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.

Περισσότερα στο USACO Guide

Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.