Output lexicographically largest DFS traversal
Company: Reevo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given a graph with `n` nodes labeled `1..n` and `m` edges. Assume an undirected graph unless stated otherwise.
You must output a node visitation sequence produced by a **depth-first search (DFS)** that visits every node exactly once overall, with these rules:
1. You may choose the start node of the first DFS.
2. When a DFS finishes (you have fully explored a connected component), if there are still unvisited nodes, you may start a new DFS from any unvisited node.
3. Within a DFS, when a node has multiple unvisited neighbors, you may choose the order to explore them.
Among all valid full-graph DFS visitation sequences of length `n`, output the **lexicographically largest** sequence (compare sequences by the first position where they differ; the one with the larger node label is larger).
Input: `n`, edge list. Output: the visitation order as `n` integers.
Quick Answer: This question evaluates understanding of graph traversal algorithms and combinatorial reasoning about node visitation order, specifically assessing the ability to manipulate depth-first search choices to produce a lexicographically maximal global sequence.