0
$\begingroup$

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.

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

In a connected component, the minimum node can reach any other node without passing by a lower index node. As your initial graph is connected, the node 0 can indeed reach any other and is the perfect root for your tree.

For any connected component, you keep the index of the node it is attached to. Initially, there is none as 0 will be te root.

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – someone12321 Jun 7 at 15:21
  • $\begingroup$ You are right it is even better as you do not have to run a DFS on each point to check if the connected component is broken. Building the tree may be a little more complex but should be okay. $\endgroup$ – Vince Jun 7 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.