uniolympiads English

Ένωση ξένων συνόλων (DSU)

Ενώνεις σύνολα και ρωτάς αν δύο στοιχεία είναι στο ίδιο, σε σχεδόν σταθερό χρόνο ανά πράξη.

Πότε

Ακμές έρχονται μία μία και ρωτάς για συνεκτικότητα: «είναι τα aa και bb συνδεδεμένα;», «πόσες συνιστώσες υπάρχουν;», «πόσο μεγάλη είναι η μεγαλύτερη;». Είναι και το μισό του Kruskal.

Η ιδέα

Κάθε σύνολο είναι ένα δέντρο, και ο εκπρόσωπός του είναι η ρίζα. Το find ανεβαίνει ως τη ρίζα. Το unite κρεμά τη μία ρίζα κάτω από την άλλη.

Δύο βελτιώσεις κάνουν τα δέντρα σχεδόν επίπεδα:

  1. Συμπίεση μονοπατιού. Μετά από κάθε find, όλοι οι κόμβοι του μονοπατιού δείχνουν κατευθείαν στη ρίζα.
  2. Ένωση κατά μέγεθος. Το μικρότερο δέντρο κρεμιέται κάτω από το μεγαλύτερο. Έτσι το ύψος μένει O(log⁡n)O(\log n) ακόμα και χωρίς συμπίεση.

Μαζί δίνουν O(α(n))O(\alpha(n)) ανά πράξη, όπου α\alpha η αντίστροφη συνάρτηση Ackermann. Στην πράξη αυτό είναι σταθερά, το πολύ 4 για κάθε nn που θα δεις.

Το find εδώ είναι επαναληπτικό. Η αναδρομική εκδοχή είναι πιο σύντομη, αλλά σε μια αλυσίδα 10610^6 κόμβων πριν από την πρώτη συμπίεση γεμίζει τη στοίβα. Το test το ελέγχει ακριβώς αυτό.

Παγίδες

  • Το unite επιστρέφει αν έγινε ένωση. Αυτό χρειάζεσαι για να μετράς συνιστώσες (ξεκινάς από nn και αφαιρείς ένα σε κάθε επιτυχία) ή για να βρίσκεις κύκλους.
  • Η DSU δεν σβήνει ακμές. Αν το πρόβλημα αφαιρεί ακμές, δοκίμασε να το τρέξεις ανάποδα, προσθέτοντάς τες.

Κώδικας

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

cpp/dsu.cpp
// Disjoint set union with path compression and union by size.
// Almost O(1) per operation (inverse Ackermann).

struct DSU {
    vector<int> parent;
    vector<int> sz;

    DSU(int n) : parent(n), sz(n, 1) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        int root = x;
        while (parent[root] != root) {
            root = parent[root];
        }
        // Second pass: point every node on the path straight to the root.
        while (parent[x] != root) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) {
            return false;
        }
        if (sz[a] < sz[b]) {
            swap(a, b);
        }
        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }

    bool same(int a, int b) {
        return find(a) == find(b);
    }

    int size(int x) {
        return sz[find(x)];
    }
};

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

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

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

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

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