Return to Question

deleted 2 characters in body

Source Link

edited Apr 29, 2020 at 20:49

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

Q1.why we need this swapping? can't we do like this without swapping

Q2.what is the difference between size array and rank array.Is Rank means the height of a node and size means no of node in that tree which contains this node

if (size[a] < size[b])
           
        parent[a] = b;
        size[b] += size[a];

Q2.what is the difference between size array and rank array.Is Rank means the height of a node and size means no of node in that tree which contains this node

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

Q1.why we need this swapping? can't we do like this without swapping

Q2.what is the difference between size array and rank array.Is Rank means the height of a node and size means no of node in that tree which contains this node

if (size[a] < size[b])
           
        parent[a] = b;
        size[b] += size[a];

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

Q1.why we need this swapping? can't we do like this without swapping

if (size[a] < size[b])
           
        parent[a] = b;
        size[b] += size[a];

Q2.what is the difference between size array and rank array.Is Rank means the height of a node and size means no of node in that tree which contains this node

Source Link

asked Apr 29, 2020 at 20:43

davinci

why swap function is use in union find algorithm? How rank or size array is used for optimization

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

Q1.why we need this swapping? can't we do like this without swapping

Q2.what is the difference between size array and rank array.Is Rank means the height of a node and size means no of node in that tree which contains this node

if (size[a] < size[b])
           
        parent[a] = b;
        size[b] += size[a];

graphs union-find