Minimum Spanning Tree (Both Prim and Kruskal)

#include <bits/stdc++.h>
#define TASK "MST"
using namespace std;
const int N = 1e5;
const long long oo = 1e18;
struct TEdge
{
    int u, v;
    long long w;
    bool select;
};
using PEdge = TEdge* ;
TEdge a[N + 1];
PEdge p[N + 1];
vector<PEdge> Adj[N + 1];
int n, m, k;
void read()
{
   cin >> n >> m;
   k = 0;
   for (int i = 1; i <= m; ++ i)
   {
       cin >> a[i].u >> a[i].v >> a[i].w;
       a[i].select = false;
       //Kruskal : p[i] = &a[i];
       /*Prim
       Adj[a[i].u].push_back(&a[i]);
       Adj[a[i].v].push_back(&a[i]); */
   }
}
// Kruskal starts from here
int lab[N + 1];
bool LF(PEdge x, PEdge y)
{
    return x->w < y->w;
}
void Unite(int r, int s)
{
    if (lab[s] <  lab[r])
    {
        swap(r, s);
    }
    lab[r] += lab[s];
    lab[s] = r;
}
int FindSet(int u)
{
    if (lab[u] < 0)
    {
        return u;
    }
    return lab[u] = FindSet(lab[u]);
}
void Kruskal()
{
    long long sum = 0;
    memset(lab, -1, sizeof(lab));
    sort(p + 1, p + m + 1, LF);
    for (int i = 1; i <= m; ++ i)
    {
        int r = FindSet(p[i]->u), s = FindSet(p[i]->v);
        if (r != s)
        {
            ++k;
            Unite(r, s);
            sum += p[i]->w;
            p[i]->select = true;
        }
    }
    if (k == n - 1)
    {
        cout << sum;
    }
    else
    {
        cout << "DISCONNECTED";
    }
}
//Prim starts from here
long long d[N + 1];
bool InTree[N + 1];
PEdge Trace[N + 1];
struct TPQItem
{
    int node;
    long long dlab;
    bool operator < (const TPQItem & other) const
    {
        return other.dlab < dlab;
    }
    bool Valid()
    {
        return d[node] == dlab;
    }
};
priority_queue<TPQItem> PQ;
void Prim()
{
   fill(d + 1, d + n + 1, oo);
   fill(InTree + 1, InTree + n + 1, false);
   d[1] = 0;
   PQ.push({1, 0LL});
   while (!PQ.empty())
   {
       TPQItem r = PQ.top();
       PQ.pop();
       if (!r.Valid())
       {
           continue;
       }
       int u = r.node;
       InTree[u] = true;
       ++k;
       for (PEdge p : Adj[u])
       {
           int v = p->u ^ p->v ^ u; // The other note except u (Spy detected)
           if (!InTree[v] && d[v] > p->w)
           {
               d[v] = p->w;
               Trace[v] = p;
               PQ.push({v, d[v]});
           }
       }
   }
   if (k != n)
   {
       cout << "DISCONNECTED";
   }
   else
   {
       long long sum = 0;
       for (int i = 2; i <= n; ++ i)
       {
           PEdge p = Trace[i];
           sum += p-> w;
       }
       cout << sum;
   }
}
void solve()
{
   //Kruskal();
   //Prim();
}
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   freopen(TASK".INP", "r", stdin);
   freopen(TASK".OUT", "w", stdout);
   int t = 1;
   bool typetest = false;
   if (typetest)
   {
      cin >> t;
   }
   for (int __ = 1; __ <= t; ++ __)
   {
      read();
      solve();
   }
}