Boruvka algoritmi - Course 3

Boruvka algoritmi - Course 3

O

(

E

)

O(E)

struct Edge {
    int u, v, weight;
};

int n;                 // cho‘qqilar soni
vector<Edge> edges;    // qirralar ro‘yxati

vector<Edge> boruvka() {
    DSU dsu(n);
    vector<Edge> mst;
    int components = n;

    while (components > 1) {
        vector<int> best_edge(n, -1);

        // har bir komponenta uchun minimal chiquvchi qirrani qidiramiz
        for (int i = 0; i < (int)edges.size(); i++) {
            int u = dsu.find_set(edges[i].u);
            int v = dsu.find_set(edges[i].v);
            if (u == v) continue;

            if (best_edge[u] == -1 || edges[i].weight < edges[best_edge[u]].weight) {
                best_edge[u] = i;
            }
            if (best_edge[v] == -1 || edges[i].weight < edges[best_edge[v]].weight) {
                best_edge[v] = i;
            }
        }

        // topilgan qirralarni qo‘shamiz
        for (int i = 0; i < n; i++) {
            if (best_edge[i] == -1) continue;

            Edge e = edges[best_edge[i]];
            int u = dsu.find_set(e.u);
            int v = dsu.find_set(e.v);
            if (u == v) continue;

            mst.push_back(e);
            dsu.union_sets(u, v);
            components--;
        }
    }

    return mst;
}