Untitled

from collections import defaultdict, deque

def max_difference(g_nodes, g_from, g_to):
    final_ans = -float('inf')

    visited = set()

    graph = defaultdict(list)
    for from_node, to_node in zip(g_from, g_to):
        graph[from_node].append(to_node)
        graph[to_node].append(from_node)

    # Conduct BFS for each node
    for start_node in graph:
        if start_node in visited:
            continue

        min_node = float('inf')
        max_node = -float('inf')

        # Here we should finish a complete BFS for each connected component
        connected_visited = set()
        queue = deque([start_node])
        component_count = 1

        connected_visited.add(start_node)
        visited.add(start_node)

        while queue:
            # Single layer of search
            for _ in range(len(queue)):
                current_node = queue.popleft()
                min_node = min(min_node, current_node)
                max_node = max(max_node, current_node)

                for next_node in graph[current_node]:
                    if next_node not in connected_visited:
                        queue.append(next_node)
                        connected_visited.add(next_node)
                        component_count += 1

        if component_count > 1:
            final_ans = max(final_ans, max_node - min_node)

    return final_ans