9. 그래프 - 예제) 팀 결성

목표

'팀합치기'연산에 따라 '같은팀 여부 확인' 을 결과를 출력해라

문제 설명

학생들은 0~N 까지의 번호 부여
처음엔 모든 학생들이 서로 다른 팀으로 분류되어 총 N+1개의 팀 존재

• 팀합치기 연산 : 0 a b 형태
• 같은팀 여부 연산 : 1 a b 형태 -> NO, YES 출력

문제를 보고나서

전형적인 서로소 집합 알고리즘 문제이다!
N, M의 범위가 모두 최대 100,000이다.
따라서 경로압축방식의 서로소 집합 자료구조를 이용해서 시간복잡도를 계산해야한다.

트리를 이용한 서로소집합 자료구조 구현 을 참고하자!

내 언어로 생각한 합집합이란?

두 집합을 합집합 = 중복을 제거하고, 같은 부모를 두게된다
코드상에서 보통 더 작은 숫자를 가진 애를 부모로 통일한다.

정답코드

# 특정 원소가 속한 집합 찾기
def find_parent(parent, x) :
	# 루트 노드가 아니라면, 루트 노드를 찾을때까지 재귀적으로 호출
    if parent[x] != x :
    	parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b) :
	a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b :
    	parent[b] = a
    else :
    	parent[a] = b

n, m = map(int, input().split())
parent [0] * (n+1) # 부모 테이블 초기화

# 부모 테이블 상에서, 부모를 자기 자신으로 초기화
for i in range(0, n+1) :
	parent[i] = i


# 각자의 연산을 하나씩 확인
for i in range(m) :
	oper, a, b = map(int, input().split())
    # 합집합(union) 연산인 경우
    if oper == 0 :
    	union_parent(parent, a, b)
    elif oper == 1 :
    	if find_parent(paretn, a) == find_parent(parent, b) :
        	print('YES')
        else :
        	print('NO')