uniolympiads English

Ισχυρά συνεκτικές συνιστώσες

Ομαδοποίηση των κορυφών ενός κατευθυνόμενου γράφου σε συνιστώσες όπου όλοι φτάνουν σε όλους, με δύο DFS, σε O(n+m)O(n + m). Από εκεί και το 2-SAT.

Πότε

«Μπορεί κάθε πόλη να φτάσει σε κάθε άλλη;», «χώρισε τους πλανήτες σε βασίλεια», και κάθε πρόβλημα όπου ένας κύκλος σε κατευθυνόμενο γράφο μπορεί να συμπτυχθεί σε μία κορυφή. Ο γράφος των συνιστωσών (η συμπύκνωση) είναι πάντα DAG.

Η ιδέα (Kosaraju)

  1. DFS σε όλο τον γράφο, κρατώντας τις κορυφές με τη σειρά που τελειώνουν.
  2. Αντιστρέφεις όλες τις ακμές. Παίρνεις τις κορυφές από αυτή που τελείωσε τελευταία προς τα πίσω. Κάθε DFS στον αντίστροφο γράφο από μια κορυφή χωρίς συνιστώσα δίνει ακριβώς μία συνιστώσα.

Γιατί δουλεύει: η κορυφή που τελειώνει τελευταία ανήκει σε μια «πηγή» της συμπύκνωσης. Στον αντίστροφο γράφο αυτή η συνιστώσα γίνεται «καταβόθρα», οπότε η DFS δεν μπορεί να βγει από αυτήν.

Έτσι οι συνιστώσες βγαίνουν σε τοπολογική σειρά της συμπύκνωσης: για κάθε ακμή u→vu \to v ανάμεσα σε διαφορετικές συνιστώσες ισχύει comp(u)<comp(v)\mathrm{comp}(u) < \mathrm{comp}(v). Το test ελέγχει και αυτό.

Και οι δύο DFS εδώ είναι επαναληπτικές, με δική τους στοίβα. Αναδρομή βάθους 2⋅1052 \cdot 10^5 ξεπερνά τη στοίβα σε πολλούς judges.

2-SAT

Στο Giant Pizza κάθε απαίτηση «xx ή yy» γίνεται δύο συνεπαγωγές, ¬x→y\lnot x \to y και ¬y→x\lnot y \to x, σε γράφο με 2m2m κορυφές (κάθε μεταβλητή και η άρνησή της). Υπάρχει λύση αν και μόνο αν καμία μεταβλητή δεν είναι στην ίδια συνιστώσα με την άρνησή της. Τότε θέτεις xx αληθές αν comp(x)>comp(¬x)\mathrm{comp}(x) > \mathrm{comp}(\lnot x).

Παγίδες

  • Η σειρά «τελειώματος» δεν είναι η σειρά επίσκεψης. Η κορυφή μπαίνει στη λίστα όταν έχουν εξεταστεί όλοι οι γείτονές της.
  • Στο 2-SAT η σύγκριση των συνιστωσών εξαρτάται από τη φορά της αρίθμησης. Με τον κώδικα αυτής της σελίδας (μικρότερο comp\mathrm{comp} = νωρίτερα στην τοπολογική σειρά) είναι >>, όπως γράφεται πιο πάνω.

Κώδικας

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

cpp/scc.cpp
// Strongly connected components, Kosaraju. O(n + m).
// comp[v] = index of v's component; components come out in topological order of the condensation
// (an edge u -> v between different components always has comp[u] < comp[v]).
// Both passes are iterative, so deep graphs (n = 2e5 on a path) do not overflow the stack.

struct SCC {
    int n;
    int count = 0;
    vector<int> comp;

    SCC(const vector<vector<int>>& adj) : n(adj.size()), comp(adj.size(), -1) {
        vector<vector<int>> radj(n);
        for (int u = 0; u < n; u++) {
            for (int v : adj[u]) {
                radj[v].push_back(u);
            }
        }
        // Pass 1: vertices in increasing finish time.
        vector<int> order;
        vector<char> seen(n, 0);
        vector<int> it(n, 0);
        for (int s = 0; s < n; s++) {
            if (seen[s]) {
                continue;
            }
            vector<int> stk = {s};
            seen[s] = 1;
            while (!stk.empty()) {
                int u = stk.back();
                if (it[u] < (int)adj[u].size()) {
                    int v = adj[u][it[u]];
                    it[u]++;
                    if (!seen[v]) {
                        seen[v] = 1;
                        stk.push_back(v);
                    }
                } else {
                    order.push_back(u);
                    stk.pop_back();
                }
            }
        }
        // Pass 2: on the reversed graph, latest finish first.
        for (int i = n - 1; i >= 0; i--) {
            int s = order[i];
            if (comp[s] != -1) {
                continue;
            }
            vector<int> stk = {s};
            comp[s] = count;
            while (!stk.empty()) {
                int u = stk.back();
                stk.pop_back();
                for (int v : radj[u]) {
                    if (comp[v] == -1) {
                        comp[v] = count;
                        stk.push_back(v);
                    }
                }
            }
            count++;
        }
    }
};

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

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

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

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

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