fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. class DSU {
  8. public:
  9.     vector<int> size;
  10.     vector<int> parent;
  11.  
  12.     DSU(int n) {
  13.         size.assign(n, 1);
  14.         parent.resize(n);
  15.         for (int i = 0; i < n; i++) parent[i] = i;
  16.     }
  17.  
  18.     int findParent(int x) {
  19.         if (x == parent[x]) return x;
  20.         return parent[x] = findParent(parent[x]); // Path compression
  21.     }
  22.  
  23.     void unionBySize(int x, int y) {
  24.         int rootX = findParent(x); // FIX: Must use findParent
  25.         int rootY = findParent(y);
  26.         if (rootX != rootY) {
  27.             if (size[rootX] < size[rootY]) swap(rootX, rootY);
  28.             parent[rootY] = rootX;
  29.             size[rootX] += size[rootY];
  30.         }
  31.     }
  32. };
  33.  
  34. int maxWeightInGraph(int threshold, vector<vector<int>> edges, int n) {
  35.     // If threshold is 0 and we have more than 1 node, it's impossible
  36.     if (threshold < 1 && n > 1) return -1;
  37.  
  38.     // 1. Sort edges by weight (Ascending)
  39.     sort(edges.begin(), edges.end(), [](const vector<int>& a, const vector<int>& b) {
  40.         return a[2] < b[2];
  41.     });
  42.  
  43.     DSU dsu(n);
  44.     int maxW = -1;
  45.  
  46.     // 2. Greedy merge (Kruskal's logic)
  47.     for (const auto& edge : edges) {
  48.         int u = edge[0];
  49.         int v = edge[1];
  50.         int w = edge[2];
  51.  
  52.         // We unite the nodes. In the context of reachability to 0, 
  53.         // we treat the connection as an undirected bridge.
  54.         dsu.unionBySize(u, v);
  55.         maxW = w;
  56.  
  57.         // 3. Check if all nodes are now in the same component as Node 0
  58.         // findParent(0) will give the root of the component containing 0.
  59.         // If that component's size is N, everyone can reach 0.
  60.         if (dsu.size[dsu.findParent(0)] == n) {
  61.             return maxW;
  62.         }
  63.     }
  64.  
  65.     return -1; // Not all nodes could be connected
  66. }
  67.  
  68. int main() {
  69.     // Example 1
  70.     vector<vector<int>> edges1 = {{1,0,2},{2,1,3},{2,3,3}};
  71.     cout << "Example 1 (Expected 1): " << maxWeightInGraph(2, edges1, 4) << endl;
  72.  
  73.     // Example 2
  74.     vector<vector<int>> edges2 = {{0,1,1},{0,2,2},{0,3,1},{0,4,1},{1,2,1},{1,4,1}};
  75.     cout << "Example 2 (Expected -1): " << maxWeightInGraph(1, edges2, 5) << endl;
  76.  
  77.     return 0;
  78. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Example 1 (Expected 1): 3
Example 2 (Expected -1): 1
https://ideone.com/NHpPTs
language:
C++ (gcc 8.3)
created:
3 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!