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)
The worst case for a single function call can be $$$O(n)$$$, but the time complexity per function call is amortized $$$O(\log n)$$$, i.e. $$$q$$$ function calls will run in $$$O(q \log n)$$$ total time.
https://stackoverflow.com/questions/56229760/what-is-the-complexity-of-path-compression-technique-for-disjoint-set-algorithm
Please google it, it's $$$\mathcal{O}(\log{}n)$$$ as can be read in cp algorithms website the more queries u use it'll be decreased, worst case will always be n but this will happen only once, after that it'll be n/2 then n/4 so for Q queries, you'll have $$$\mathcal{O}(Q\log{}n)$$$ (harmonic series)
CP algorithms says:
you can see, cp-algo doesn't proof the time complexity of the path compression-only approach, and its proof is not that easy as you think. btw you can read "Tarjan-van Leeuwen (1984)" paper for complete proof (I also had this question one day and after searching I found this paper).