# 2424. Longest Uploaded Prefix
###### tags: `Leetcode` `Medium` `Union Find`
Link: https://leetcode.com/problems/longest-uploaded-prefix/description/
## 思路
每次新进来一个video 如果它的前一个或者后一个出现过 就merge起来
注意combine起来的时候 往小的方向combine 这样longest()里面return size[1]就可以了
## Code

class LUPrefix {
    int[] fa;
    int[] size;
    boolean[] exist; 
    int n;
    
    public LUPrefix(int n) {
        this.n = n;
        fa = new int[n+1];
        size = new int[n+1];
        exist = new boolean[n+1];
        for(int i=1; i<=n; i++) fa[i] = i;
        for(int i=1; i<=n; i++) size[i] = 1;
    }
    
    public void upload(int video) {
        exist[video] = true;
        if(video-1!=0 && exist[video-1]){
            combine(video-1, video);
        }
        if(video+1<=n && exist[video+1]){
            combine(video, video+1);
        }
    }
    
    public int longest() {
        return exist[1]?size[1]:0;
    }
    
    private int find(int a){
        if(fa[a]==a) return a;
        else return fa[a]=find(fa[a]);
    }
    
    private void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return;
        if(a<b){
            fa[b] = a;
            size[a] += size[b];
        }
        else{
            fa[a] = b;
            size[b] += size[a];
        }
    }
}