Boruvka's algorithm starts with each vertex as its own component. In each phase, every component selects its minimum outgoing edge, and all selected edges are added at once. Components merge until one remains.
struct DSU {
vector<int> p, r;
DSU(int n): p(n), r(n,0) { iota(p.begin(), p.end(), 0); }
int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
bool unite(int a,int b){
a=find(a); b=find(b);
if(a==b) return false;
if(r[a]<r[b]) swap(a,b);
p[b]=a;
if(r[a]==r[b]) r[a]++;
return true;
}
};
int boruvkaMST(int n, vector<tuple<int,int,int>>& edges){
DSU dsu(n);
int components=n, total=0;
while(components>1){
vector<int> best(n,-1);
for(int i=0;i<(int)edges.size();i++){
auto [w,u,v]=edges[i];
int ru=dsu.find(u), rv=dsu.find(v);
if(ru==rv) continue;
if(best[ru]==-1 || get<0>(edges[best[ru]])>w) best[ru]=i;
if(best[rv]==-1 || get<0>(edges[best[rv]])>w) best[rv]=i;
}
for(int i=0;i<n;i++) if(best[i]!=-1){
auto [w,u,v]=edges[best[i]];
if(dsu.unite(u,v)){ total+=w; components--; }
}
}
return total;
}Each component picks one cheapest outgoing edge in each round.
Multiple edges can be added per phase, shrinking components rapidly.
Disjoint set structure tracks component IDs efficiently.
Quiz coming soon for this algorithm.