C++ Union-Find amotrized O(n)
class Solution {\n        vector<int> id;\n        vector<int> size;\n    public:\n        int longestConsecutive(vector<int>& nums) {\n            int n = nums
    class Solution {\n        vector<int> id;\n        vector<int> size;\n    public:\n        int longestConsecutive(vector<int>& nums) {\n            int n = nums.size();\n            if(n < 2) return n;\n            size = vector<int>(n,1);\n            for(int i = 0; i < n; i++) {\n                id.push_back(i);\n            }\n            unordered_map<int,int> record;\n            for(int i = 0 ; i < n; i++) {\n                if(record.find(nums[i]) != record.end()) continue;\n                record[nums[i]] = i;\n                if(record.find(nums[i]-1) != record.end()) {\n                    unionSet(i,record[nums[i]-1]);\n                }\n                if(record.find(nums[i]+1) != record.end()) {\n                    unionSet(i,record[nums[i]+1]);\n                }\n            }\n            int res = *max_element(size.begin(),size.end());\n            return res;\n        }\n        \n        int find(int p) {\n            while(p != id[p]) {\n                id[p] = id[id[p]];\n                p = id[p];\n            }\n            return p;\n        }\n        void unionSet(int a, int b) {\n            int i = find(a);\n            int j = find(b);\n            if(i == j) return;\n            if(size[i] > size[j]) {\n                id[j] = i;\n                size[i] += size[j];\n            } else {\n                id[i] = j;\n                size[j] += size[i];\n            }\n        }\n    };
[]