WHAT IS THE WORST CASE OF (DSU) WHEN I USE PATH COMPRESSION ONLY

Revision en2, by mostafaabdelaal_03, 2024-03-02 21:33:55
int n;
vector<int>p, v;
int get(int a){
    return p[a] = (a==p[a]) ? a : get(p[a]);   
}
void unin(int a, int b){
    a = get(a);
    b = get(b);
    p[a] = b;
}
I implemented  this code when I was solving problems about Dsu in section Edu..now if I used path compression in get function but I donot Consider the samllest set and larget set in union ..can the comlexity reach O(N)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English mostafaabdelaal_03 2024-03-02 21:33:55 2 Tiny change: ' reach O(N^2)\n~~~~~\n' -> ' reach O(N)\n~~~~~\n'
en1 English mostafaabdelaal_03 2024-03-02 20:04:22 496 Initial revision (published)