[그래프] 팀 결성

1. 문제 설명

팀을 결성하기 위해 학생과 학생을 묶고, 학생과 학생이 같은 팀인지 확인하는 문제.

- 학생들을 같은 팀으로 묶는 함수가 존재하고(union_parent), 학생들이 같은 팀인지 확인하는 함수가 존재한다.(same_parent)

2. 코드

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
        
def same_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a == b:
        return "YES"
    else:
        return "NO"

n, m = map(int, input().split())

# 부모 리스트 초기화
parent = [i for i in range(n+1)]

result = []
for _ in range(m):
    a, b, c = map(int, input().split())
    if a == 0:
        union_parent(parent, b, c)
    elif a == 1:
        result.append(same_parent(parent, b, c))
        
for i in result:
    print(i)
    
    
 """
 7 8
0 1 3 
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1
>> NO
   NO 
   YES
"""

3. 코멘트

- 서로소 집합을 활용한 문제로 find_parent함수와 union_parent함수를 잘 이해해야 풀 수 있는 문제라고 생각한다. 

- 그래프 이론의 경우 DP적인 개념도 포함되어 있는 것 같다.