Untitled
unknown
python
a year ago
1.4 kB
10
Indexable
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
Editor is loading...
Leave a Comment