서로소 집합 알고리즘

	import sys
	def find_parent(x):
	if parent[x] != x:
	parent[x] = find_parent(parent[x])
	return parent[x]
	def union_parent(x, y):
	x = find_parent(x)
	y = find_parent(y)
	if x < y:
	parent[y] = x
	else:
	parent[x] = y
	n, m = map(int, input().split())
	parent = [0]*(n+1)
	for i in range(1, n+1):
	parent[i] = i
	for i in range(m):
	x, y = map(int, sys.stdin.readline().split())
	union_parent(x, y)
	s = set()
	for i in range(1, n+1):
	s.add(find_parent(i))
	if len(s) == 1:
	print(1)
	else:
	print(len(s))

view raw 백준 연결 요소의 개수 - 서로소 집합 사용 hosted with ❤ by GitHub

find_parent(x) 메소드가 최상단 부모 노드를 바로 재귀적으로 찾아 반환해 준다. 이를 이용하는 union_parent(x, y) 메소드는 두 노드를 비교하여 작은 노드를 큰 노드의 부모 노드로 연결시킨다. 해당 문제는 연결 요소의 개수를 세는 문제이므로 union_parent(x, y)을 통해 연결을 끝낸 뒤 각 노드의 부모노드를 set 자료형 안에 담아서 해결했다.