Help Regarding Disjoint Set Union(DSU)

help
,
1

When i use these two different versions of unite function in my dsu code i get different answer can someone help what is the reason

Code Snippet 1:

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b)
        parent[b] = a;
}

Code Snippet 2:

void union_sets(int a, int b) {
    int x = find_set(a);
    int y = find_set(b);
    if (x!= y)
        parent[b] = x;
}
2

Code snippet two is wrong.

1 Like
3

Think of the value parent as a statement like “I belong to the same group as that node”. To quickly check two items a,b belong to the same group you need to find a chain of statements a\rightsquigarrow c and b\rightsquigarrow c. Because each item only remembers one other member of their group you can only form one chain from a and one chain from b.

To make the DSU work we need to make sure that following the parent chain from each item of a groups ends up in the same place, the “root” of that group. These roots is what you search for with the find_set lines.
When joining two groups we need to maintain this property. For that we choose one of the two original group roots as the new group root. The other one (the one that now isn’t a group root anymore) must then have a path to the new group root. This is achieved by code snippet 1 by setting the parent directly. However code snippet 2 doesn’t do that because there is not a path from item y to item b.