백준 1717_ Python

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

1717번: 집합의 표현

 

문제

---

초기에 {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 를 출력해도 된다)

 

 

접근법

---

1. union 기법을 사용해서 문제에 접근을 하게된다.
2. 첫번째 기법은 union 하는 함수를 만드는 건데, merge()로 이름붙여 함수를 구현하였다. merge(a,b)를 받게된다면, parent[b]=a 로 함으로써, b의 부모를 a로 만들어준다
3. 두번째 함수는 find 함수로써 parent[a]!= a 일시 , parent[a] = find(parent[a]) 를 반복해줌으로써, 최상위 부모를 찾아주는 함수이다.

 

import sys 
n, m = map(int, sys.stdin.readline().split())
parent = list([i for i in range(0,n+1)])

def find(a):
	if parent[a] != a:
    	parent[a] = find(parent[a])
    return parent[a]
   
 
 def merge(a,b):
 	a = find(a)
    b = find(b)
    parent[b] = a
    return

for i in range(m):
	a,b,c = map(int, sys.stdin.readline().split())
    if a ==0:
    	merge(b,c)
    else:
    	if find(b) = find(c): print("YES")
        else: print("NO")