문제 링크

• https://www.acmicpc.net/problem/1717

문제 설명

• 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다

• 0, a, b 일 때, a가 속한 집합과 b가 속한 집합을 합한다

• 1, a, b 일 때, a가 속한 집합과 b가 속한 집합이 같은지 출력

틀린 풀이

• 그대로 구현
  • 시간초과
• 합집합 -> 에지 연결 -> DFS
  • 시간초과
  • 특정 좌표를 찾아야만 재귀가 종료하기 때문?
  • 루트가 같기만 하면 같은 집합

맞은 풀이

• 각 수마다 부모 노드를 저장하는 리스트 생성

• 1, a, b 일 때

  • a와 b의 루트 노드를 각각 찾는다
  • 같으면 yes, 다르면 no

• 0, a, b 일 때

  • a와 b의 루트 노드를 각각 찾는다

  • 다를 경우

    • a의 루트 노드의 부모 = b의 루트 노드 (순서 무관)

Union 과정

• 0 1 3 결과
  
• 0 7 6 결과
  
• 0 3 7 결과
  
• 0 4 2 결과
  

코드

import sys


def union(a, b):
    ra = get_root(a)
    rb = get_root(b)
    if ra != rb:
        parent[rb] = ra


def get_root(x):
    if parent[x] != x:
        parent[x] = get_root(parent[x])
    return parent[x]


sys.setrecursionlimit(10000)
ipt = sys.stdin.readline
opt = sys.stdout.write
n, m = map(int, ipt().split())
parent = list(range(n+1))
for _ in range(m):
    check, a, b = map(int, ipt().split())
    if a > b:
        a, b = b, a
    if check:
        ra = get_root(a)
        rb = get_root(b)
        if ra == rb:
            opt('yes\n')
        else:
            opt('no\n')
    else:
        union(a, b)