Different Approach than normal graph traversal


I have used the data structure Disjoint Set Union (Union Find).

The complexity can be reduced to Log*N which is faster than LogN.


Can you elaborate on how you did it with disjoint set union ? Is it that you consider each node having a value of ‘X’ as a parent individually first and then merge the adjacent nodes which have ‘X’ on them and finally count how many total connected components are there ? Can you share the code ?