CSES. Road Reparation

1.Problem

https://cses.fi/problemset/task/1675

2.Idea

Standard MST with UnionFind implementation

3.Source

 int n, m;  
 struct Edge {  
      int u, v, c;  
      bool operator < (const Edge &a)const {  
           return c < a.c;  
      }  
 } Edges[N];  
 struct UF {  
      vector<int> Parent;  
      vector<int> Size;  
      int Count;  
      void init(int n) {  
           Count = n;  
           Parent.resize(n);  
           Size.resize(n);  
           REP(i, n) {  
                make_set(i);  
           }  
      }  
      void make_set(int v) {  
           Parent[v] = v;  
           Size[v] = 1;  
      }  
      int find_set(int v) {  
           if (v == Parent[v])  
                return v;  
           return Parent[v] = find_set(Parent[v]);  
      }  
      void union_sets(int a, int b) {  
           a = find_set(a);  
           b = find_set(b);  
           if (a != b) {  
                if (Size[a] < Size[b])  
                     swap(a, b);  
                Count--;  
                Parent[b] = a;  
                Size[a] += Size[b];  
           }  
      }  
 };  
 void solve()  
 {  
      cin >> n >> m;  
      REP(i, m) {  
           cin >> Edges[i].u >> Edges[i].v >> Edges[i].c;  
           Edges[i].u--;  
           Edges[i].v--;  
      }  
      sort(Edges, Edges + m);  
      UF uf;  
      uf.init(n);  
      Int ret = 0;  
      REP(i, m) {  
           int u = Edges[i].u;  
           int v = Edges[i].v;  
           int c = Edges[i].c;  
           if (uf.find_set(u) != uf.find_set(v)) {  
                ret += c;  
                uf.union_sets(u, v);  
           }  
      }  
      if (uf.Count == 1) cout << ret << endl;  
      else cout << "IMPOSSIBLE" << endl;  
 }