Untitled

public class Solution {

    private void dfs(Map<Integer, List<Pair>> nodes, int v, Set<Integer> seen) {
        seen.add(v);
        for (Pair u : nodes.get(v)) {
            if (!seen.contains(u.key)) {
                dfs(nodes, u.key, seen);
            }
        }
    }

    private int getCountOfConnectivityComponent(Map<Integer, List<Pair>> graph) {
        Set<Integer> seen = new HashSet<>();
        int comps = 0;

        for (int v : new ArrayList<>(graph.keySet())) {
            if (!seen.contains(v)) {
                dfs(graph, v, seen);
                comps++;
            }
        }
        return comps;
    }

    private Map<Integer, List<Pair>> removeRoadsLessThanX(Map<Integer, List<Pair>> graph, int x) {
        for (Map.Entry<Integer, List<Pair>> entry : graph.entrySet()) {
            List<Pair> roads = entry.getValue();
            List<Pair> filteredRoads = new ArrayList<>();
            for (Pair pair : roads) {
                if (pair.value > x) {
                    filteredRoads.add(pair);
                }
            }
            entry.setValue(filteredRoads);
        }
        return graph;
    }

    public int findX(int n, int m, int[][] roads) {
        Map<Integer, List<Pair>> graph = new HashMap<>();
        for (int[] road : roads) {
            int start = road[0];
            int end = road[1];
            int weight = road[2];
            graph.computeIfAbsent(start, k -> new ArrayList<>()).add(new Pair(end, weight));
            graph.computeIfAbsent(end, k -> new ArrayList<>()).add(new Pair(start, weight));
        }

        int baseCountOfStates = getCountOfConnectivityComponent(graph);
        Arrays.sort(roads, Comparator.comparingInt(x1 -> x1[2]));

        int left = 0, right = n - 1;
        int x = -1;

        while (left <= right) {
            int middle = (right + left) / 2;
            int tmpX = roads[middle][2];

            Map<Integer, List<Pair>> tmpGraph = new HashMap<>(graph);
            tmpGraph = removeRoadsLessThanX(tmpGraph, tmpX);
            int newCountOfStates = getCountOfConnectivityComponent(tmpGraph);

            if (newCountOfStates > baseCountOfStates) {
                right = middle - 1;
                x = tmpX - 1;
            } else {
                left = middle + 1;
            }
        }

        return x;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 5;
        int m = 6;
        int[][] roads = {
                {1, 2, 8},
                {2, 3, 6},
                {2, 3, 2},
                {3, 1, 4},
                {5, 4, 1},
                {4, 5, 8}
        };
        int result = solution.findX(n, m, roads);
        System.out.println(result); // Вывод результата
    }
}

class Pair {
    int key;
    int value;

    Pair(int key, int value) {
        this.key = key;
        this.value = value;
    }
}