Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.3 kB
2
Indexable
Never
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]