[C++] 팀 결성

1. 문제

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

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

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

2. 입력 조건

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

3. 출력 조건

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

4. 풀이

• 서로소 집합과 관련된 문제이다.
• 팀 합치기 연산은 union으로 같은 팀 여부 확인 연산은 find로 구현한다.
• 처음 시작하면 모든 노드의 부모를 자기 자신으로 초기화한다.
• 그 후로 팀 합치기(unionParent) 연산이 들어올 때마다 a 혹은 b 학생의 부모를 변경한다.
  부모는 어느 쪽으로 변경해도 상관없으나 일반적으로 숫자가 작은 쪽이 부모가 되게 한다.
• 같은 팀 여부 확인(findParent)을 할 때는 각 학생의 부모 노드를 찾는다. 부모 노드를 찾는 연산은 자신의 인덱스와 인덱스에 해당하는 배열의 값이 같으면 자신이 부모 노드이고 그렇지 않으면 재귀적으로 자신의 부모를 찾아 최종 부모를 찾는다.
• 최종 부모가 같은 학생은 같은 팀에 있는 학생이다.

5. 처음 코드와 달라진 점

• null

6. 코드

#include <iostream>

using namespace std;

int v, e;
int parent[100001];

int findParent(int x) {
  if(parent[x] == x) return x;
  else return findParent(parent[x]);
}

void unionParent(int a, int b) {
  a = findParent(a);
  b = findParent(b);

  if(a < b) parent[b] = a;
  else parent[a] = b;
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  cin>>v>>e;

  for (int i = 0; i <= v; i++) {
    parent[i] = i;
  }
  
  for (int i = 0; i < e; i++) {
    int op, a, b;
    cin>>op>>a>>b;

    if(op == 0) { 
      unionParent(a, b);
    }
    else {
      if(findParent(a) == findParent(b)) cout<<"YES";
      else cout<<"NO";
    }
  }
}