팀 결성(파이썬) / 사이클 체크

문제

• 학교에서 학생들에게 0번부터 N번까지 팀 번호를 부여ㅑ했다.
• 모든 학생이 다른 팀으로 시작하는데 이 때, 연산을 통해서 팀이 결성된다.
• 1. '팀 합치기' 연산은 두 팀을 합치는 연산이다.
• 2. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다.
• 선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력해라.

 

입력

• 첫째 줄에 N, M(연산횟수) 이 주어진다(1<=N,M <= 100,000).
• 다음 M 개의 줄에는 각각 연산이 주어진다
• '팀 합치기' 연산은 0 a b 로 주어지는데 a,b 팀을 합친다
• '같은 팀 여부 확인' 연산은 1 a b 로 주어진다.

 

출력

• '같은 팀 여부 확인' 연산에 대해 같으면 YES 다르면 NO를 출력

"INPUT"
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

"OUTPUT"
NO
NO
YES

---

import sys

sys.stdin = open("input_10-2.txt" ,"r")
sys.stdout = open("ouput_10-2.txt", "w")

# 부모 찾기
def get_parent(parent, a):
    a_parent = a
    while True:
        if parent[a_parent] == a_parent:
            return a_parent
        else:
            a_parent = parent[a_parent]

# 합치기
def union_parent(parent, a_p, b_p):
    # 같을 경우 아무것도 안함
    if a_p == b_p:
        return 0
    # 그 외 index 작은 순
    elif a_p < b_p:
        parent[b_p] = a_p
    else:
        parent[a_p] = b_p

# input
n, m = map(int,input().split())
parent = [i for i in range(0,n+1)]

# main
for _ in range(m):
    cmd, a, b = map(int, input().split())

    # 합치기
    if cmd == 0:
       union_parent(parent, get_parent(parent, a), get_parent(parent, b))

    # 출력
    elif cmd == 1:
        # 같을 경우
        if get_parent(parent, a) == get_parent(parent, b):
            print('YES')
        else:
            print('NO')