Nerd-sniping: Disjoint Set Union/ Union-Find Data Structure for Directed Graph

[Shubham Kumar]

Dear Friends,

Disjoint Set Union/ Union-Find Data structure helps maintain information about disjoint sets such that union operation on them and finding whether two elements are from the same subset or not, are highly optimized operation. After two known optimizations viz. Path compression and Union by Size/ Rank, the amortized time complexity of find and union operation become inverse Ackermannn function which is extremely slow growing and all for all practical purposes is less than five. 

One disadvantage of this above data structure is that it does not generalize well for directed graphs. The topology information is somewhat lost. 

Does one know about the equivalent data structure for directed graph? The suggested data structure should support find and union operation efficiently.  

Best Regards,

Shubham Kumar

P.S. This definitely emerged out of my present work but for now I am not going in this direction further. I am just curious to learn about this new data structure if it exists and in later implementations can incorporate it.