Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.1 kB
2
Indexable
Never
from collections import defaultdict

def distinctOrder(g_nodes, g_from, g_to):
    # Create an adjacency list representation of the graph
    graph = defaultdict(list)
    for i in range(len(g_from)):
        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
    def dfs(graph, node, visited):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(graph, neighbor, visited)

    # Perform DFS and store visited nodes in a set
    visited = set()
    dfs(graph, max(graph), visited)

    # 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]