[알고리즘][Python] 백준(BOJ) 1717 집합의 표현_파이썬

 

1717 집합의 표현    www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

 

 

 

문제 풀기 전 공부할 것 : 자료구조, 분리 집합

 

 

 

 

 

 

 

풀이

<내용>

• Union-Find를 이용해서 해결할 수 있다.
• parent를 자기 자신으로 초기화한다.
• 부모를 찾는 find 함수를 만든다.
• 합집합 연산을 하여 같은 부모를 갖도록 union 함수를 만든다.
• 연산을 입력받아 0이면 union으로 합집합 연산을 하고 1인 경우 find를 통해 부모를 찾고 부모가 같으면 같은 집합, 다르면 다른 집합에 포함되어 있는 것이다.

 

 

<코드>

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
parent = [i for i in range(n+1)]

def find(target):
    if target == parent[target]:
        return target
    
    parent[target] = find(parent[target])
    return parent[target]

def union(a, b):
    a = find(a)
    b = find(b)
    
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
for _ in range(m):
    flag, a, b = map(int, input().split())
    if flag:
        if find(a) == find(b):
            print('YES')
        else:
            print('NO')
        
    else:
        union(a, b)