# How to build tree from graph with specific property

We are given connected undirected graph of $$n$$ nodes and $$m$$ edges. On each node one integer(value) from $$0$$ to $$n-1$$ is written.

We need to build tree such that for each node $$i$$, all nodes in the subtree of $$i$$ should be reachable from $$i$$ by going only through edges with values greater than $$i$$.

Such tree is always rooted at $$0$$ since all vertices can be reached from $$0$$.

For example, for the given graph:

(5, 1), (1, 2), (1, 3), (3, 4), (3, 0), (5, 2)
The tree we are looking for is rooted at 0 and its edges are:
(0, 1), (1, 2), (1, 3), (2, 5), (3, 4)


I have heard that this is solvable with using disjoint data set structure however I couldn't find a way how to properly find a way to connect the components.

• The tree with 0 connected to every other vertex is always a solution. Do you have an additionnal constraint ? – Optidad Jun 7 '19 at 13:08
• Subtree of node $i$ should contain all nodes reachable from $i$ with visiting only nodes with values(indexes) greater than $i$. – someone12321 Jun 7 '19 at 13:16
• Ok please edit your question to make the double inclusion visible. – Optidad Jun 7 '19 at 13:40

Once you considered the minimum node of a connected component, you can remove it as no other node in the CC may use it. Let's call this node $$k$$, you add $$k$$ to its place in the tree you are building, as child of the node index of the connected component.
Then either the connected component is still connected and its new index is $$k$$, either it is cut in several connected components, all having $$k$$ as index.
• Instead of removing nodes, I thought of inserting nodes, one good thing is that we can insert them in decreasing direction (from N-1 to 0), and for each node only process the edges that link this node to node with higher value. So for each connected component we will keep two roots: one root in order to maintain the $O(logN)$ DSU data structure and one root that shows which is the minimum node in this connected component. I wonder if this will work? – someone12321 Jun 7 '19 at 15:21