Τοπολογική ταξινόμηση
Σειρά των κορυφών ενός DAG ώστε κάθε ακμή να πηγαίνει προς τα εμπρός, σε . Πάνω της τρέχει κάθε DP σε DAG.
Πότε
Εξαρτήσεις («το μάθημα πριν από το »), ή DP σε κατευθυνόμενο γράφο χωρίς κύκλους: μακρύτερη διαδρομή, πλήθος διαδρομών, κάτι που υπολογίζεται από τους προκατόχους.
Η ιδέα (Kahn)
Μια κορυφή χωρίς εισερχόμενες ακμές μπορεί να μπει πρώτη. Τη βάζεις, σβήνεις τις ακμές της, και κάποιες άλλες κορυφές μένουν χωρίς εισερχόμενες. Κρατάς τον βαθμό εισόδου κάθε κορυφής και μια ουρά με όσες έχουν βαθμό 0.
Αν στο τέλος έχουν βγει λιγότερες από κορυφές, οι υπόλοιπες έχουν πάντα κάποια εισερχόμενη ακμή μεταξύ τους. Άρα υπάρχει κύκλος, και η συνάρτηση επιστρέφει κενό.
DP σε DAG
Στο Longest Flight Route υπολογίζεις τη μακρύτερη διαδρομή από το στο . Διατρέχεις τις κορυφές με την τοπολογική σειρά, οπότε όταν φτάνεις στο έχουν ήδη τελειώσει όλοι οι προκάτοχοί του:
Στο Game Routes το ίδιο με άθροισμα αντί για μέγιστο, modulo .
Παγίδες
- Η τοπολογική σειρά δεν είναι μοναδική. Αν το πρόβλημα θέλει τη λεξικογραφικά μικρότερη, αντικατέστησε την ουρά με
priority_queue(ελάχιστο πρώτο). - Στο
Longest Flight Routeκορυφές που δεν είναι προσβάσιμες από το δεν πρέπει να δίνουν τιμή. Ξεκίνα με παντού εκτός από το .
Κώδικας
Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.
// 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
Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.
- Course Schedule · Graph Algorithms
- Longest Flight Route · Graph Algorithms
- Game Routes · Graph Algorithms
Περισσότερα στο USACO Guide
- Topological Sort · usaco.guide/gold/toposort
Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.