Skip to main content

Algorithms · Dynamic programming and state design

Given an undirected graph with up to five million vertices, produce exactly the…

Problem

Algorithms practice problem

Given an undirected graph with up to five million vertices, produce exactly the preorder, postorder, parent array, and subtree sizes defined by recursive depth-first search that starts at vertex 11 and examines neighbors in increasing order. Only vertices reachable from vertex 11 are included in the two orders; every unreachable vertex has parent 00 and subtree size 00. Program recursion is prohibited, and auxiliary memory beyond the graph representation and output arrays is limited to O(n)O(n) machine words. The input satisfies 1≤n≤5,000,0001\le n\le 5{,}000{,}000 and 0≤m≤8,000,0000\le m\le 8{,}000{,}000.

Hint

Hint

** A recursive call remembers both its vertex and where its neighbor loop should resume.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Algorithms sample problem: Try the free sample problem.

More Algorithms practice problems

Back to Algorithms

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.