https://www.acmicpc.net/problem/1717
1717번: 집합의 표현
첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는
www.acmicpc.net
<코드>
import sys
input = sys.stdin.readline
def find_set(x):
if p[x] == x:
return x
parent = find_set(p[x])
p[x] = parent
return parent
def union(a, b):
p_a = find_set(a)
p_b = find_set(b)
p[p_b] = p_a
n, m = map(int, input().split())
p = [i for i in range(n+1)]
for _ in range(m):
a, b, c = map(int,input().split())
if a == 0:
union(b,c)
elif a == 1:
if find_set(b) == find_set(c):
print('YES')
else:
print('NO')
<풀이과정>
union-find 알고리즘으로 풀어야되는데 몰라서 구글링 + 유명 블로그를 참고하였다.
'파이썬' 카테고리의 다른 글
[프로그래머스 파이썬] 124 나라의 숫자 (0) | 2022.08.30 |
---|---|
[파이썬 백준] 1406번 에디터 (0) | 2022.08.29 |
[백준 파이썬] 2589번 보물섬 (0) | 2022.08.27 |
[백준 파이썬] 5014번 스타트링크 (0) | 2022.08.26 |
[백준 파이썬] 1850번 최대공약수 (0) | 2022.08.24 |