DSU - DOUBT

Why doesn’t the DSU work for directed graphs?

So there is problem,

Which can be solved by the usual DSU

But i cannot wrap my head around this https://leetcode.com/problems/redundant-connection-ii/

The exact same problem but for Directed graph…Can someone help in this problem

lets assume it is possible … then lets say that 1 is connected to 3, and 3 is connected to 5 and 1 is connected to 7 (here i mean directed edges) ,which means that 1 3 5 7 are in the same component and we know that we can go from any vertex to any other in a single component but that is not the case , we cant go from 3 to 7 nor 5 to 7 nor 5 to 1 … etc.

@vai53
Using DSU for the undirected problem seems pretty straight forward. But I do not understand what logic you would use for the directed problem.
Can you post the algorithm that you would use, in brief?

@shahayush2507 What you say is true, however, we can store the root of the component in the DSU array. This will work because only the root has an in-degree of 0, and every other node has an in-degree of at least 1 (in the non modified tree). While processing the edges, if we connect two nodes, which have the same root, then this is our extra edge.
Is my approach wrong?

I’m sorry but i don’t understand this, could you explain it to me a little more briefly.

There are some answers in LC discuss…with DSU approach. I din’t understand much

According to the given definition of a directed tree, the root must only have edges going out of it. And there is only one such node in the entire tree.

So when we add the edges one by one, we’ll be having a forest initially, which eventually converges to a single tree. Each tree in the current forest can be uniquely identified by the special root node (which has in-degree 0, i.e., no incoming edges to this node).

When merging, we will merge two trees, and the root node of the new tree will be one of the roots of the old trees. Out of the two old roots, the new root can be identified by the direction of the edge being added. If the new edge is connecting a node from tree2 to tree1, then the new root of the combined tree will be the root of tree1.

During this process of merging, if we add an edge within a tree (that is two nodes have the same parent in the DSU), then this is the extra edge.

@vai53, did you understand this approach?

1 Like

sort of, i will get back if i have a doubt…

1 Like

Well, I don’t think my approach is entirely right. There might be flaws. I tried to implement this in leetcode and I’m getting an RE. If I find a flaw, or a better algorithm, I’ll post it here.

1 Like

I think this should help.

1 Like