Untitled
unknown
plain_text
2 years ago
1.3 kB
4
Indexable
def distinctOrder(g_nodes, g_from, g_to): # Create an adjacency list representation of the graph graph = {} for i in range(len(g_from)): if g_from[i] not in graph: graph[g_from[i]] = [] if g_to[i] not in graph: graph[g_to[i]] = [] graph[g_from[i]].append(g_to[i]) graph[g_to[i]].append(g_from[i]) # Sort the adjacency lists to make sure we get the lexicographically largest traversal for key in graph: graph[key].sort(reverse=True) # Function to perform BFS traversal def bfs(graph, start_node): visited = set() queue = [start_node] while queue: node = queue.pop(0) if node not in visited: visited.add(node) queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited) return visited # Perform BFS and store visited nodes in a set visited = bfs(graph, max(graph)) # Sort the visited nodes in descending order (lexicographically largest array) B = sorted(visited, reverse=True) return B g_nodes = 5 g_from = [4, 5, 1, 4, 3] g_to = [5, 1, 4, 3, 2] result = distinctOrder(g_nodes, g_from, g_to) print(result) # Output: [5, 4, 3, 2, 1]
Editor is loading...