# Leetcode 128. Longest Consecutive Sequence

## 題解

### Set

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        output = 0
        nums_set = set(nums)

        for num in nums_set:
            if num - 1 not in nums_set:
                cn = num
                ans = 1
                while cn + 1 in nums_set:
                    cn = cn + 1
                    ans += 1
                output = max(output,ans)
        
        return output

### Union Find

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        uf = UnionFind()
        nodes = {}
        max_size = 0
        for num in nums:
            if num not in nodes:
                node = Node(num)    
                nodes[num] = node
                size = 1
                if num + 1 in nodes:
                    size = uf.union(node, nodes[num+1])
                if num - 1 in nodes:
                    size = uf.union(node, nodes[num-1])
                max_size = max(max_size, size)
        return max_size
    
class Node:
    def __init__(self, val):
        self.val = val
        self.parent = self
        self.size = 1
    
class UnionFind:
    def find(self, node):
        if node.parent != node:
            node.parent = self.find(node.parent)
        return node.parent
    
    def union(self, node_u, node_v):
        root_u = self.find(node_u)
        root_v = self.find(node_v)
        if root_u != root_v:
            root_v.parent = root_u
            root_u.size += root_v.size
        return root_u.size