Untitled
unknown
plain_text
2 years ago
1.4 kB
2
Indexable
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; }
Editor is loading...