1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

//128最长连续序列，并查集
//in：nums = [100,4,200,1,3,2]
//4
//in：nums = [0,3,7,2,5,8,4,6,0,1]
//9
unordered_map<int, int> fa, cnt;
int find0(int x) {
    //无压缩find
    while (fa[x] != x)
        x = fa[x];//向上找
    return x;//return root
}
int find(int x) {
    //压缩路径，fa[x]==root
    if (fa[x] == x)
        return x;//出口，root
    return fa[x] = find(fa[x]);
}
int join(int x, int y) {
    //合并，修改每颗合并后的层高
    x = find(x);
    y = find(y);
    if (x==y)	return cnt[x];
    if (cnt[x] > cnt[y]) {
        fa[y] = x;
        cnt[x] += cnt[y];
        return cnt[x];
    } else {
        fa[x] = y;
        cnt[y] += cnt[x];
        return cnt[y];
    }
}
int longestConsecutive(vector<int>& nums) {
    if (!nums.size()) return 0;
    for (auto x : nums) {
        //让每个num自成一个子树，指定层高为1
        fa[x] = x;
        cnt[x] = 1;
    }
    int res = 1;
    for (auto x : nums) {
        //遍历nums，如果x+1也在nums中，则合并这两个子树
        if (fa.count(x+1)) {
            //统计合并后子树层高，与之前的res取大的一个
            res = max(res, join(x, x+1));
        }
    }
    return res;
}