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.
Return the lexicographically largest full-graph DFS visitation sequence for an undirected graph.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (5, [[1,2],[1,3],[4,5]])
Expected Output: [5, 4, 3, 1, 2]
Explanation: Start each component from highest unvisited node and take highest neighbors first.
Input: (3, [[1,2],[2,3]])
Expected Output: [3, 2, 1]
Explanation: Connected path starts at node 3.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.