팀 결성 [theory of graph] #이것이 코딩테스트다

[문제] 팀 결성: 문제 설명

학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다.처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N + 1개의 팀이 존재한다.이때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다.

    1. '팀 합치기' 연산은 두 팀을 합치는 연산이다.
    2. ‘같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다.

선생님이 M개의 연산을 수행할 수 있을 때,'같은 팀 여부 확인' 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오.

난이도: ●●○| 풀이시간 20m | 시간제한 2초 | 메모리 128mb

 

<input case>

첫째 줄에 N, M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. (1 <= N, M <= 100,000)
다음 M개의 줄에는 각각의 연산이 주어진다.'팀 합치기' 연산은 0 a b 형태로 주어진다.이는 a번 학생이 속한 팀과 b번 학생이 속한 팀을 합친다는 의미이다.
'같은 팀 여부 확인' 연산은 1 a b 형태로 주어진다.이는 a번 학생과 b번 학생이 같은 팀에 속해 있는지를 확인하는 연산이다.
a와 b는 N 이하의 양의 정수이다

 

 

<Output case>

'같은 팀 여부 확인' 연산에 대하여 한 줄에 하나씩 YES 혹은 NO로 결과를 출력한다.

input example	Output example
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

<Idea>

Q. 간단한 문제네 그냥 연산 구현하라는데 이문제는 구현파트에 들어가야하지 않았을까?
A. 그러게 ㅋㅋㅋㅋ

def find_team(parent,x): #결국 본인 트리의 최상단을 찾는 함수
  if parent[x] != x: find_team(parent, parent[x])
  return parent[x]

def union_team(parent, a, b): #2개의 트리를 연결시키는 함수
  a= find_team(parent,a)
  b= find_team(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(n+1):  parent[i]=i

for _ in range(m):
  x, a, b=map(int, input().split())
  if x==0:  union_team(parent, a, b)
  else: 
    if find_team(parent, a) == find_team(parent, b): print("YES")
    else: print("NO")