Question 13
Back to Exercise
What is the output of the following Java program?
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Map<String, List<String>> g = new HashMap<>();
String[][] edges = {{"A", "C"}, {"A", "B"}, {"C", "D"}, {"B", "E"}, {"D", "F"}};
for (String[] e : edges) g.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
List<String> order = new ArrayList<>();
Set<String> seen = new HashSet<>();
Deque<String> stack = new ArrayDeque<>();
stack.push("A");
while (!stack.isEmpty()) {
String u = stack.pop();
if (!seen.add(u)) continue;
order.add(u);
for (String v : g.getOrDefault(u, List.of())) stack.push(v);
}
System.out.println(order);
}
}
- A [A, C, B, D, E, F]
- B [A, C, D, F, B, E]
- C [A, B, C, D, E, F]
- D [A, B, E, C, D, F] Correct
Correct Answer: Option D
C is pushed before B, so B is on top and explored first. Recursive DFS would give [A, C, D, F, B, E]; push neighbours in reverse to match it.
Discussion & Comments 0
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!