Even Outdegree Edges

Problems and Contests
#1

Link

This is in the Tree Algorithms module under silver. I don’t really understand what is the inspiration of a spanning tree? Why can we greedily assign the edge directions using a DFS, instead of finding the DFS tree?

#2

How do you DFS without finding a DFS tree? :thinking:

1 Like
#3

Just do normal DFS on a graph, and then greedily assign directions for each node. Is that what the solution mean by DFS tree? Maybe I misunderstood?

#4

I completely don’t understand the solution of this problem posted on USACO Guide (https://usaco.guide/problems/cses-2179-even-outdegree-edges/solution), can someone please explain this?

#5

You probably might want to read this blog post (it’s linked in the usaco guide solution) on dfs tree and its properties + applications.