Finding dfs tree

Initially, regard every vertex as a separate component. Vertices joined by already selected tree edges are contracted into one component.

An incoming edge of a current component $B$ is an original directed edge whose tail is outside $B$ and whose head is inside $B$. Count edges themselves, not the number of distinct source components.

Find a component $B$ with exactly one incoming edge. Let that edge be $u \to v$, and let $A$ be the component containing $u$. Select $u \to v$ as a tree edge, set $P_v=u$, and merge $A$ and $B$. The root vertex of the merged component is the former root vertex of $A$.

Repeat until no such contraction is possible.

Correctness

Suppose $B$ has the unique incoming edge $u \to v$ and is attached below $A$. This is the only edge directed from the $A$ side to the $B$ side. Therefore, every other edge that becomes internal when the two components are merged is directed from $B$ to . Such an edge points from the descendant component to the ancestor component in the newly constructed tree. Conditions inside the old components remain valid by induction.

Conversely, suppose a valid tree exists and more than one component remains. Contract every current component in that valid tree. The component tree has a leaf component. Exactly one tree edge enters this leaf from its parent component. No non-tree back edge can additionally enter it, because there is no descendant component outside the leaf component. Hence some component has exactly one incoming edge.

Eligible contractions can be exchanged. A contraction does not change the incoming-edge set of any unrelated component; it only replaces its two involved components by their union. Therefore, if a complete contraction sequence exists, any currently eligible contraction may be performed first.

If one component remains, the selected $N-1$ edges form a valid tree. If several components remain and none has exactly one incoming edge, no valid tree exists.

Efficient implementation

For every component, store:

• the list of its vertices,
• a hash set of edge indices entering the component from outside,
• the component root whose parent has not been assigned.

When merging two components, move the component with fewer vertices into the larger one.

Inspect all outgoing edges of vertices in the smaller component to erase edges that become internal from the larger component's incoming-edge set. Move the smaller incoming-edge set into the larger set, discarding edges whose tails are already in the larger component.

Whenever a vertex moves, the size of its component at least doubles. Thus every vertex and edge is processed only $O(\log N)$ times. With hash sets, the expected time complexity is $O((N+M)\log N)$ and the memory complexity is $O(N+M)$.