uniolympiads English

Ελάχιστο συνδετικό δέντρο (Kruskal)

Ταξινομείς τις ακμές κατά βάρος και κρατάς όσες ενώνουν δύο διαφορετικές συνιστώσες. O(mlog⁡m)O(m \log m), με DSU.

Πότε

Θέλεις να συνδέσεις όλες τις κορυφές με το ελάχιστο συνολικό κόστος. Ή, συχνότερα στους διαγωνισμούς, θέλεις μια ιδιότητα του MST: «ποιο είναι το μέγιστο βάρος που πρέπει να διασχίσεις για να πας από το aa στο bb, στην καλύτερη περίπτωση;» Η απάντηση είναι η βαρύτερη ακμή στο μονοπάτι του MST.

Η ιδέα

Ιδιότητα τομής: για κάθε διαμέριση των κορυφών σε δύο μέρη, η ελαφρύτερη ακμή που τα συνδέει ανήκει σε κάποιο MST. Ο Kruskal την εφαρμόζει άπληστα. Περνάει τις ακμές από την ελαφρύτερη. Όταν μια ακμή ενώνει δύο συνιστώσες, είναι η ελαφρύτερη που διασχίζει την τομή «αυτή η συνιστώσα / όλα τα άλλα», άρα την κρατάμε. Αν οι άκρες της είναι ήδη στην ίδια συνιστώσα, θα έκλεινε κύκλο, άρα την πετάμε.

Ο κώδικας χρειάζεται τη DSU. Αν ο γράφος δεν είναι συνεκτικός, επιστρέφει το βάρος ενός ελάχιστου συνδετικού δάσους. Για να ξέρεις αν υπάρχει δέντρο, μέτρα τις ακμές που κράτησες: πρέπει να είναι n−1n - 1.

Παγίδες

  • Στο Road Reparation η απάντηση είναι IMPOSSIBLE όταν ο γράφος δεν είναι συνεκτικός. Αυτό είναι το «μέτρα τις ακμές» πιο πάνω.
  • Τα βάρη αθροίζονται σε long long: 2⋅1052 \cdot 10^5 ακμές επί 10910^9.

Κώδικας

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

cpp/kruskal.cpp
// Minimum spanning tree (forest), Kruskal. O(m log m) for the sort.
// Needs dsu.cpp. Edges in increasing weight; keep an edge when it joins two components.
// Returns the total weight; if the graph is disconnected, it is the weight of a minimum spanning forest.

struct WeightedEdge {
    int u;
    int v;
    ll w;
};

ll kruskal(int n, vector<WeightedEdge> edges, vector<WeightedEdge>* chosen = nullptr) {
    sort(edges.begin(), edges.end(), [](const WeightedEdge& a, const WeightedEdge& b) {
        return a.w < b.w;
    });
    DSU dsu(n);
    ll total = 0;
    for (const WeightedEdge& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            total += e.w;
            if (chosen != nullptr) {
                chosen->push_back(e);
            }
        }
    }
    return total;
}

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

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

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

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

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