# Path: permuta/misc/union_find.py
# class UnionFind:
#     """A collection of distjoint sets."""
# 
#     def __init__(self, size: int) -> None:
#         """Creates a collection of size disjoint unit sets."""
#         self._parent = [-1] * size
# 
#     def find(self, idx: int) -> int:
#         """Return the identifier of a representative element for the set
#         containing the element with identifier idx."""
#         if self._parent[idx] < 0:
#             return idx
#         self._parent[idx] = self.find(self._parent[idx])
#         return self._parent[idx]
# 
#     def size(self, idx: int) -> int:
#         """Return the number of elements in the set containing the element with
#         identifier idx."""
#         return -self._parent[self.find(idx)]
# 
#     def unite(self, idx1: int, idx2: int) -> bool:
#         """Unite the two sets containing the elements with identifiers idx1 and idx2,
#         respectively."""
#         idx1, idx2 = self.find(idx1), self.find(idx2)
#         if idx1 == idx2:
#             return False
#         if self.size(idx1) > self.size(idx2):
#             idx1, idx2 = idx2, idx1
#         self._parent[idx2] += self._parent[idx1]
#         self._parent[idx1] = idx2
#         return True


import random
from itertools import combinations
from permuta.misc.union_find import UnionFind
    assert uf.find(1) == uf.find(3)
    assert uf.size(1) == uf.size(3) == uf.size(8) == 3
    assert all(uf.size(i) == 1 for i in range(10) if i not in (1, 3, 8))


def test_union_find_2():
    uf = UnionFind(100)
    for i in range(1, 100):
        assert uf.unite(0, i)
    for (a, b) in combinations(range(100), 2):
        assert uf.find(a) == uf.find(b)
        assert uf.size(a) == 100
        assert uf.size(b) == 100


def test_union_find_3():
    uf = UnionFind(4)
    assert uf.find(0) == uf.find(0)
    assert not uf.unite(0, 0)
    assert uf.unite(1, 0)
    assert not uf.unite(0, 1)
    assert uf.unite(1, 2)
    assert not uf.unite(1, 2)
    assert not uf.unite(0, 2)
    assert uf.find(0) != uf.find(3)


def test_union_find_4():
    n = 5000
    d = {i: {i} for i in range(n)}

# Path: permuta/misc/union_find.py
# class UnionFind:
#     """A collection of distjoint sets."""
# 
#     def __init__(self, size: int) -> None:
#         """Creates a collection of size disjoint unit sets."""
#         self._parent = [-1] * size
# 
#     def find(self, idx: int) -> int:
#         """Return the identifier of a representative element for the set
#         containing the element with identifier idx."""
#         if self._parent[idx] < 0:
#             return idx
#         self._parent[idx] = self.find(self._parent[idx])
#         return self._parent[idx]
# 
#     def size(self, idx: int) -> int:
#         """Return the number of elements in the set containing the element with
#         identifier idx."""
#         return -self._parent[self.find(idx)]
# 
#     def unite(self, idx1: int, idx2: int) -> bool:
#         """Unite the two sets containing the elements with identifiers idx1 and idx2,
#         respectively."""
#         idx1, idx2 = self.find(idx1), self.find(idx2)
#         if idx1 == idx2:
#             return False
#         if self.size(idx1) > self.size(idx2):
#             idx1, idx2 = idx2, idx1
#         self._parent[idx2] += self._parent[idx1]
#         self._parent[idx1] = idx2
#         return True


# Path: tests/misc/test_union_find.py
import random
from itertools import combinations
from permuta.misc.union_find import UnionFind

    assert uf.find(1) == uf.find(3)
    assert uf.size(1) == uf.size(3) == uf.size(8) == 3
    assert all(uf.size(i) == 1 for i in range(10) if i not in (1, 3, 8))


def test_union_find_2():
    uf = UnionFind(100)
    for i in range(1, 100):
        assert uf.unite(0, i)
    for (a, b) in combinations(range(100), 2):
        assert uf.find(a) == uf.find(b)
        assert uf.size(a) == 100
        assert uf.size(b) == 100


def test_union_find_3():
    uf = UnionFind(4)
    assert uf.find(0) == uf.find(0)
    assert not uf.unite(0, 0)
    assert uf.unite(1, 0)
    assert not uf.unite(0, 1)
    assert uf.unite(1, 2)
    assert not uf.unite(1, 2)
    assert not uf.unite(0, 2)
    assert uf.find(0) != uf.find(3)


def test_union_find_4():
    n = 5000
    d = {i: {i} for i in range(n)}

    uf = UnionFind(n)