Disjoint_Set.ipynb

{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"provenance":[],"authorship_tag":"ABX9TyPUVa8xUWm1cX0it8uGSCW0"},"kernelspec":{"name":"python3","display_name":"Python 3"},"language_info":{"name":"python"}},"cells":[{"cell_type":"code","execution_count":null,"metadata":{"id":"cvqRPdUgg1Sg"},"outputs":[],"source":["def find(x: int, parents: list[int]) -> tuple[int, list[int]]:\n","    \"\"\"서로소 집합에서 부모를 찾는 함수\n","\n","    Args:\n","        x: 노드 번호\n","        parents: 부모 리스트\n","\n","    Returns:\n","        (부모 번호, 부모 리스트)\n","    \"\"\"\n","\n","    if x != parents[x]:\n","        parents[x] = find(x=parents[x], parents=parents)\n","    return parents[x]\n","\n","\n","def union(x: int, y: int, parents: list[int], rank: list[int]) -> tuple[list[int], list[int]]:\n","    \"\"\"서로소 집합에서 두 집합을 합치는 함수\n","    합칠 때 빠른 연산을 위해 모든 하위 노드의 부모 번호를 갱신하지 않으므로 주의할 것!\n","\n","    Args:\n","        x: 첫번째 집합\n","        y: 두번째 집합\n","        parents: 부모 리스트\n","        rank: 랭크 리스트\n","\n","    Returns:\n","        (부모 리스트, 랭크 리스트)\n","    \"\"\"\n","\n","    x, y = find(x=x, parents=parents), find(x=y, parents=parents)\n","\n","    if rank[x] > rank[y]:\n","        parents[y] = x\n","    else:\n","        parents[x] = y\n","\n","    # 랭크가 같은 경우 부모가 된 y노드의 랭크를 1만큼 증가\n","    if rank[x] == rank[y]:\n","        rank[y] += 1\n","\n","    return parents, rank"]}]}