반대로 생각해서 집합A의 어디에 있는 원소가 마지막 행에 있을 가능성이 높을지 생각해보면 그냥 집합 A를 마지막부터 첫번째까지 검증해보면 됨
원소는 나중에 들어온게 뒤에 있으니 중간에 마지막행이 아닌게 나오면 거기서 중단하면 되는거임
이 검증 작업은 스택을 써도 유용할듯?
어쨋든 전수조사할 필요가 없고 최악의 경우에도 열의 갯수만큼만 검증하면 됨

집합이 원소에 대한 정보를 담고 있을거 아님
원소가 자기 자신이 어느 집합에 속하는지 저장할 수도 있지만 반대로 집합이 자기 자신에 속하는 원소를 저장할 수도 있으니 집합 기준으로 원소를 선택하면 행의 모든 방을 탐색할 필요가 없음.
 HashSet은 그냥 예시를 든건데 모르면 그냥 흘려들어도 됨. 사실은 병합 부분보다 집합에 어떤 원소가 속하는지 확인하는 작업이 O(1)의 상수 시간 복잡도를 갖는다는 게 더 중요함

대충 흐름을 보여주기 위한 pseudo code

# O(root(n))
for j in range(width): 
    # 초기화 

# O(root(n))
for i in range(height):
    # 전 행 기준으로 한칸 내리기: O(root(n)) => sample하는 원소의 개수는 항상 width보다 작거나 같음
    for s in sets:
        selected = sample(s, randint(1, len(s))
        for _, j in seleted:
            s.add((i, j))
    # 빈곳 채우기: O(root(n))
    for j in range(width):
        sets.add({(i, j)})

    # 옆으로 뚫기: O(root(n))
    holes = sample(range(width - 1), randint(0, width - 1))
    for j in holes:
        # get_set은 상수 시간 복잡도를 갖는다고 가정
        set_left, set_right = get_set(i, j), get_set(i, j + 1) 
        if set_left is not set_right:
            set_left |= set_right
            sets.remove(set_right)
# O(root(n))
for j in range(width):
    # 마지막 행 완성

>> 시간복잡도: O(root(n) + n + root(n)) = O(n)