Union Find - C++
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class DSU{
    public:
    vector<int> par,size;
   
    DSU(int n){
        par.resize(n);
        size.resize(n,1);
        for(int i=0;i<n;i++){
            par[i]=i;
        }
    }

    int findUPar(int node){
        if(par[node]==node) return node;

        return par[node] = findUPar(par[node]);
    }

    void unionBySize(int u, int v){
        int up_u = findUPar(u);
        int up_v = findUPar(v);

        if(up_u==up_v) return;
        else if(size[up_u]<size[up_v]){
            par[up_u] = up_v;
            size[up_v]+=size[up_u];
        } else {
            par[up_v] = up_u;
            size[up_u]+=size[up_v];
        }
     
    }
};
class LUPrefix {
public:
    vector<int> vis;
    int x = 0;
    DSU ds;
    LUPrefix(int n): ds(n+1) {
  
        vis.resize(n+1,0);
    }
    
    void upload(int video) {
        vis[video] = 1;
        // for(int i=1;i<vis.size()-1;i++){
        //     if(vis[i]==0 || vis[i+1]==0)
        //       break;

        //     ds.unionBySize(i,i+1);  
        // }
        if(vis.size()-1 > 1){
               if(video==1){
                if(vis[video+1]==1)
                  ds.unionBySize(video,video+1);
        } else if(video == vis.size()-1){
                   
             if(vis[video-1]==1)
                 ds.unionBySize(video,video-1);

        } else {
               if(vis[video+1]==1)
                     ds.unionBySize(video,video+1);

                if(vis[video-1]==1)
                     ds.unionBySize(video,video-1);
        }
        }

        
    }
    
    int longest() {

        if(vis.size()-1==1)
           return vis[1] == 1;
        
        return vis[1]==0?0:ds.size[ds.findUPar(1)];
    }
};

/**
 * Your LUPrefix object will be instantiated and called as such:
 * LUPrefix* obj = new LUPrefix(n);
 * obj->upload(video);
 * int param_2 = obj->longest();
 */
```
['Union Find', 'C++']