fork download
copy 
  1. struct Edge
  2. {
  3.     ll u, v, cost;
  4.     Edge(ll u, ll v, ll cost) : u(u), v(v), cost(cost) {}
  5.     bool operator<(const Edge &e) const { return cost < e.cost; }
  6. };
  7.  
  8. struct DSU
  9. {
  10.     vector<ll> parent, size; // Representative
  11.     // The leader should be the parent of itself
  12.     DSU(int n)
  13.     {
  14.         parent.resize(n + 1);
  15.         size.resize(n + 1, 1); // Each component if of size 1 initially
  16.         iota(parent.begin(), parent.end(), 0);
  17.     }
  18.     ll representative(ll node)
  19.     {
  20.         // Small to large technique
  21.         if (parent[node] == node)
  22.             return node;
  23.  
  24.         return parent[node] = representative(parent[node]); // Path compression
  25.     }
  26.     void Union(ll u, ll v)
  27.     {
  28.         ll rep1 = representative(u);
  29.         ll rep2 = representative(v);
  30.         if (rep1 == rep2)
  31.             return;
  32.         if (size[rep1] > size[rep2])
  33.             swap(rep1, rep2); // representative of smaller set comes first
  34.         parent[rep1] = rep2;
  35.         size[rep2] += size[rep1];
  36.     }
  37.     bool isSameComponent(ll u, ll v)
  38.     {
  39.         return (representative(u) == representative(v));
  40.     }
  41.     map<ll, ll> findConnectedComponents(int N)
  42.     {
  43.         map<ll, ll> components;
  44.         for (int i = 1; i <= N; i++)
  45.         {
  46.             ll root = representative(i);
  47.             components[root]++;
  48.         }
  49.         return components;
  50.     }
  51. };
  52.  
  53. int main()
  54. {
  55.     ios_base::sync_with_stdio(false);
  56.     cin.tie(nullptr);
  57.     int t = 1;
  58.     ll N, M, A;
  59.     // cin >> t;
  60.     while (t--)
  61.     {
  62.         cin >> N >> M >> A;
  63.         vector<Edge> graph;
  64.         DSU disjointSet(N + 1);
  65.         for (int i{}; i < M; i++)
  66.         {
  67.             ll u, v, c;
  68.             cin >> u >> v >> c;
  69.             graph.push_back({u, v, c});
  70.         }
  71.         sort(graph.begin(), graph.end()); // Sort edges by cost
  72.  
  73.         // Kruskal's MST logic
  74.         ll mstCost = 0;
  75.  
  76.         for (const auto &[u, v, cost] : graph)
  77.         {
  78.             if (!disjointSet.isSameComponent(u, v))
  79.             {
  80.                 disjointSet.Union(u, v);
  81.                 mstCost += cost;
  82.             }
  83.         }
  84.     }
  85.     return 0;
  86. }
Success #stdin #stdout #stderr 0.26s 40880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Error: unexpected symbol in "struct Edge"
Execution halted
https://ideone.com/2UvmRM
language:
R (R 3.5.2)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!