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
    Map<Integer, List<Integer>> graph = new HashMap<>();
    for (int i = 0; i < gFrom.size(); i++) {
        int from = gFrom.get(i);
        int to = gTo.get(i);
        graph.putIfAbsent(from, new ArrayList<>());
        graph.putIfAbsent(to, new ArrayList<>());
        graph.get(from).add(to);
        graph.get(to).add(from);
    }

    // Sort the adjacency lists to make sure we get the lexicographically largest traversal
    for (List<Integer> neighbors : graph.values()) {
        Collections.sort(neighbors, Collections.reverseOrder());
    }

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

    // 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(Map<Integer, List<Integer>> graph, int startNode) {
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();
    queue.add(startNode);

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