Untitled

 avatar
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...