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.

Improve this question
$\endgroup$
3
  • $\begingroup$ The tree with 0 connected to every other vertex is always a solution. Do you have an additionnal constraint ? $\endgroup$ Commented Jun 7, 2019 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$ Commented Jun 7, 2019 at 13:16
  • $\begingroup$ Ok please edit your question to make the double inclusion visible. $\endgroup$ Commented Jun 7, 2019 at 13:40

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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$ Commented Jun 7, 2019 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$ Commented Jun 7, 2019 at 15:27

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.