cswork / libraryOpen practice workspace

Coding questions · Reevo

Output lexicographically largest DFS traversal

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.

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.

Lexicographically Largest DFS Traversal

Examples

Example 1

Input: (5, [[1,2],[1,3],[4,5]])
Output: [5, 4, 3, 1, 2]

Explanation: Start each component from highest unvisited node and take highest neighbors first.

Example 2

Input: (3, [[1,2],[2,3]])
Output: [3, 2, 1]

Explanation: Connected path starts at node 3.

Hints

  1. Clarify edge cases before coding.
  2. Keep the return value deterministic.