# Untitled

unknown
plain_text
a year ago
3.0 kB
4
Indexable
Never
```public class Solution {

private void dfs(Map<Integer, List<Pair>> nodes, int v, Set<Integer> seen) {
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()) {
for (Pair pair : roads) {
if (pair.value > x) {
}
}
}
return graph;
}

public int findX(int n, int m, int[][] roads) {
Map<Integer, List<Pair>> graph = new HashMap<>();
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);

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

while (left <= right) {
int middle = (right + left) / 2;

Map<Integer, List<Pair>> tmpGraph = new HashMap<>(graph);
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;
{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;
}
}```