Untitled

class Solution:

    def dfs(self, nodes, v, seen: set):
        seen.add(v)
        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:
        for start, roads in graph.items():
            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)
        sorted_roads = sorted(roads, key=lambda x1: x1[2])

        left, right = 0, n - 1

        x = -1
        while left <= right:
            midd = (right + left) // 2
            tmp_x: int = sorted_roads[midd][2]

            tmp_graph = self.remove_all_roads_less_than_x(deepcopy(graph), tmp_x)
            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