Ένωση ξένων συνόλων (DSU)
Ενώνεις σύνολα και ρωτάς αν δύο στοιχεία είναι στο ίδιο, σε σχεδόν σταθερό χρόνο ανά πράξη.
Πότε
Ακμές έρχονται μία μία και ρωτάς για συνεκτικότητα: «είναι τα και συνδεδεμένα;», «πόσες συνιστώσες υπάρχουν;», «πόσο μεγάλη είναι η μεγαλύτερη;». Είναι και το μισό του Kruskal.
Η ιδέα
Κάθε σύνολο είναι ένα δέντρο, και ο εκπρόσωπός του είναι η ρίζα. Το find ανεβαίνει ως τη ρίζα. Το unite κρεμά τη μία ρίζα κάτω από την άλλη.
Δύο βελτιώσεις κάνουν τα δέντρα σχεδόν επίπεδα:
- Συμπίεση μονοπατιού. Μετά από κάθε
find, όλοι οι κόμβοι του μονοπατιού δείχνουν κατευθείαν στη ρίζα. - Ένωση κατά μέγεθος. Το μικρότερο δέντρο κρεμιέται κάτω από το μεγαλύτερο. Έτσι το ύψος μένει ακόμα και χωρίς συμπίεση.
Μαζί δίνουν ανά πράξη, όπου η αντίστροφη συνάρτηση Ackermann. Στην πράξη αυτό είναι σταθερά, το πολύ 4 για κάθε που θα δεις.
Το find εδώ είναι επαναληπτικό. Η αναδρομική εκδοχή είναι πιο σύντομη, αλλά σε μια αλυσίδα κόμβων πριν από την πρώτη συμπίεση γεμίζει τη στοίβα. Το test το ελέγχει ακριβώς αυτό.
Παγίδες
- Το
uniteεπιστρέφει αν έγινε ένωση. Αυτό χρειάζεσαι για να μετράς συνιστώσες (ξεκινάς από και αφαιρείς ένα σε κάθε επιτυχία) ή για να βρίσκεις κύκλους. - Η DSU δεν σβήνει ακμές. Αν το πρόβλημα αφαιρεί ακμές, δοκίμασε να το τρέξεις ανάποδα, προσθέτοντάς τες.
Κώδικας
Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.
// 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
Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.
- Building Roads · Graph Algorithms
- Road Construction · Graph Algorithms
Περισσότερα στο USACO Guide
- Disjoint Set Union · usaco.guide/gold/dsu
Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.