We can use a Map to map each node from the original graph to the new graph. dfs use dfs to traverse the graph. time: O(E + V) space: O(V) bfs use bfs to traverse the graph. time: O(E + V) space: O(V)