Untitled
unknown
plain_text
2 years ago
1.3 kB
6
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 DFS traversal iteratively def dfs_iterative(graph, start_node): visited = set() stack = [start_node] while stack: node = stack.pop() if node not in visited: visited.add(node) stack.extend(neighbor for neighbor in graph[node] if neighbor not in visited) return visited # Perform iterative DFS and store visited nodes in a set visited = dfs_iterative(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
Editor is loading...