Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.4 kB
1
Indexable
Never


public static List<Integer> distinctOrder(int gNodes, List<Integer> gFrom, List<Integer> gTo) {
    // Create an adjacency list representation of the graph
    List<Integer>[] graph = new ArrayList[gNodes + 1];
    for (int i = 1; i <= gNodes; i++) {
        graph[i] = new ArrayList<>();
    }

    for (int i = 0; i < gFrom.size(); i++) {
        int from = gFrom.get(i);
        int to = gTo.get(i);
        graph[from].add(to);
        graph[to].add(from);
    }

    // Sort the adjacency lists to make sure we get the lexicographically largest traversal
    for (int i = 1; i <= gNodes; i++) {
        Collections.sort(graph[i], Collections.reverseOrder());
    }

    // Perform BFS and store visited nodes in a set
    Set<Integer> visited = bfs(graph, gNodes);

    // Sort the visited nodes in descending order (lexicographically largest array)
    List<Integer> B = new ArrayList<>(visited);
    B.sort(Collections.reverseOrder());

    return B;
}

private static Set<Integer> bfs(List<Integer>[] graph, int startNode) {
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
    queue.add(startNode);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        if (!visited.contains(node)) {
            visited.add(node);
            queue.addAll(graph[node]);
        }
    }
    return visited;
}