Search code examples
algorithmunion-find

How to find id of union find operation


I am studying Union Find.

Union Find

I understand how these union operations come together to make this graph but I do not understand how the ID variable is assigned. At first, I thought it was the size of each graph but this is not true because the size of the first graph is 5 and the size of the second one is 3. Any help would be appreciated.


Solution

  • Normally in the array ID, the index represents a node of any of the graphs and the associated value is the root of the graph that belongs to. So in the example here:

    • The node 0 (firs element) is associated with 6, because 0 belongs to a graph where 6 is the root.
    • The node 1 is also associated with 6, because 1 belongs to a graph where 6 is the root.
    • [...]
    • In the same way, 4, 5 7 are associated to 4 because these nodes belong to the graph where 4 is the root.

    It's a way to quickly identify if two nodes are connected