class Disjoint{
vector<int> size,parent;
public:
Disjoint(int n){
parent.resize(n+1);
size.resize(n+1, 1);
for(int i=0; i<=n; i++)
parent[i] = i;
}
int find_ultimate_parent(int node){
if(parent[node] == node)
return node;
return parent[node] = find_ultimate_parent(parent[node]);
}
void union_by_size(int u, int v){
int ul_u = find_ultimate_parent(u);
int ul_v = find_ultimate_parent(v);
if(ul_u == ul_v)
return ;
if(size[ul_u] > size[ul_v]){
parent[ul_v] = ul_u;
size[ul_u] += size[ul_v];
}
else{
parent[ul_u] = ul_v;
size[ul_v] += size[ul_u];
}
}
};
class Solution
{
public:
int spanningTree(int V, vector<vector<int>> adj[]){
vector<pair<int, pair<int,int>>> edges;
for(int i=0; i<V; i++){
for(auto &it: adj[i]){
int neigh = it[0], wt = it[1];
edges.push_back({wt,{neigh, i}});
}
}
sort(edges.begin(), edges.end());
int ans = 0;
Disjoint ds(V);
for(auto &it: edges){
int wt = it.first;
int neigh = it.second.first, node = it.second.second;
if(ds.find_ultimate_parent(neigh) != ds.find_ultimate_parent(node)){
ans += wt;
ds.union_by_size(neigh, node);
}
}
return ans;
}
};