백준 1717번 집합의 표현 파이썬 유니온 파인드 골드4

chldkato.tistory.com/84

모르겠어서 인강도 보고 블로그도 보고 했는데 여러 모로 찝찝한 문제.

이유를 알수 없이 변수 위치만 바꿔줬는데 틀리던게 맞다고 했다.

문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

구현

import sys
input = sys.stdin.readline
mm={}
def find_parent(x):
    if mm[x]==x:
        return x
    else:
        return find_parent(mm[x])
def get_parent(x):
    if mm[x]==x:
        return x
    else:
        mm[x]=get_parent(mm[x])
        return mm[x]
def union(x,y):
    x=get_parent(x)
    y=get_parent(y)    
    if x!=y:
        mm[y]=x
        
        
n,m = map(int, input().split())
for i in range(n+1):
    mm[i]=i
for _ in range(m):
    try:
        v,a,b=map(int, input().split())
        if not v:
            union(a,b)
        elif find_parent(a)==find_parent(b):
            print("YES") 
        else:
            print("NO")
    except:
        pass