CSES - Shared codeLink to this code: https://cses.fi/paste/82c444931deb3540a18f75/
#include <bits/stdc++.h>
#define uwu return 0;
using namespace std;
const int SIZE = 1e5 + 5;
const long long INF = 1e18 + 7;
struct edge{
int u, v, id;
long long w;
edge(int _u, int _v, int _id, long long _w) : u(_u), v(_v), id(_id), w(_w) {};
};
vector<edge> graph[SIZE];
vector <int> forest[SIZE];
int cc[SIZE];
bool been[2 * SIZE];
edge min_edge(edge e1, edge e2){
if(e1.w == e2.w)
return (e1.id < e2.id ? e1 : e2);
return (e1.w < e2.w ? e1 : e2);
}
int cc_ptr = 0;
void set_cc(int nd, int rt){
cc[nd] = cc_ptr;
for(auto i:forest[nd]){
if(i != rt)
set_cc(i, nd);
}
return;
}
edge find_safe_edge(int nd, int rt){
edge ret(nd, 0, 0, INF);
for(auto i:graph[nd]){
if(cc[nd] != cc[i.v])
ret = min_edge(ret, i);
}
for(auto i:forest[nd]){
if(i != rt)
ret = min_edge(ret, find_safe_edge(i, nd));
}
return ret;
}
long long Boruvka(int V){
for (int i = 1; i <= V; i++){
cc[i] = 0;
}
cc_ptr = 0;
vector <edge> edge_vec;
for (int i = 1; i <= V; i++){
if(!cc[i]){
cc_ptr++;
set_cc(i, 0);
edge_vec.push_back(find_safe_edge(i, 0));
}
}
if(cc_ptr == 1)
return 0;
long long sum_w = 0;
for(auto i:edge_vec){
if(!been[i.id]){
forest[i.u].push_back(i.v);
forest[i.v].push_back(i.u);
been[i.id] = 1;
sum_w += i.w;
}
}
return sum_w;
}
int main(){
int V, E;
cin >> V >> E;
for (int u, v, w, i = 1; i <= E; i++){
cin >> u >> v >> w;
edge eu(u, v, i, w), ev(v, u, i, w);
graph[u].push_back(eu);
graph[v].push_back(ev);
}
long long ans = 0;
for (int i = 0; i <= __lg(V); i++){
ans += Boruvka(V);
if(ans > INF)
break;
}
if(ans < INF)
cout << ans << '\n';
else
cout << "IMPOSSIBLE\n";
uwu
}