Graph partitioning problem

Problem

Divide a network of data centers into optimal local regions.

Given a network of g_nodes data centers and g_edges bidirectional connections, the i-th connection connects data centers g_from [i] and g_to(i) with a latency of g_weight[i]. The max_latency of a network is the maximum latency of any connection.

Divide this network into k or fewer networks by removing some of the connections such that the maximum latencies of all the regions are minimized. Find the minimum possible value of the maximum max-latency of the networks formed.

Example
Suppose g_nodes =3, m=3, k=2, g_from =[1,2,3], g_to =[2,3,1], and g_weight =[4,5,3]

Answer

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
private:
    std::vector<int> parent;

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px != py) {
            parent[px] = py;
        }
    }

    int countComponents(int n, const std::vector<std::vector<int>>& edges, int maxLatency) {
        parent.resize(n + 1);
        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
        }

        for (const auto& edge : edges) {
            if (edge[2] <= maxLatency) {
                unite(edge[0], edge[1]);
            }
        }

        int components = 0;
        for (int i = 1; i <= n; ++i) {
            if (parent[i] == i) {
                components++;
            }
        }
        return components;
    }

public:
    int findMinMaxLatency(int g_nodes, int g_edges, int k, const std::vector<int>& g_from, 
                          const std::vector<int>& g_to, const std::vector<int>& g_weight) {
        std::vector<std::vector<int>> edges(g_edges);
        for (int i = 0; i < g_edges; ++i) {
            edges[i] = {g_from[i], g_to[i], g_weight[i]};
        }

        std::sort(edges.begin(), edges.end(), 
                  [](const std::vector<int>& a, const std::vector<int>& b) {
                      return a[2] < b[2];
                  });

        int low = edges[0][2], high = edges.back()[2];

        while (low < high) {
            int mid = low + (high - low) / 2;
            if (countComponents(g_nodes, edges, mid) <= k) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        return low;
    }
};

int main() {
    Solution sol;
    int g_nodes = 3, g_edges = 3, k = 2;
    std::vector<int> g_from = {1, 2, 3};
    std::vector<int> g_to = {2, 3, 1};
    std::vector<int> g_weight = {4, 5, 3};

    std::cout << sol.findMinMaxLatency(g_nodes, g_edges, k, g_from, g_to, g_weight) << std::endl;
    return 0;
}