# Untitled

unknown
plain_text
a year ago
1.9 kB
4
Indexable
Never
```from collections import defaultdict
from copy import deepcopy
from typing import List, Dict

from test_cases import test_cases

class Solution:

def dfs(self, nodes, v, seen: set):
for u in nodes[v]:
if u[0] not in seen:
self.dfs(nodes, u[0], seen)

def get_count_of_connectivity_component(self, graph):
seen = set()
comps = 0

for v in deepcopy(graph):
if v not in seen:
self.dfs(graph, v, seen)
comps += 1
return comps

def remove_all_roads_less_than_x(self, graph, x) -> Dict:
graph[start] = list(filter(lambda i: i[1] > x, roads))
return graph

def find_x(self, n, m, roads: List[List[int]]) -> int:
graph = defaultdict(list)
for start, end, weight in roads:
graph[start].append((end, weight))
graph[end].append((start, weight))

base_count_of_states = self.get_count_of_connectivity_component(graph)

left, right = 0, n - 1

x = -1
while left <= right:
midd = (right + left) // 2

new_count_of_states = self.get_count_of_connectivity_component(tmp_graph)

if new_count_of_states > base_count_of_states:
right = midd - 1
x = tmp_x - 1
else:
left = midd + 1

return x

test_cases(
func=Solution().find_x,