Untitled
plain_text
19 days ago
3.0 kB
4
Indexable
Never
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; } }