[백준] 1717번 집합의 표현 c++

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

 

문제접근 및 풀이

union find 알고리즘을 연습할 수 있는 좋은 문제이다.

- 각 줄의 첫째 숫자가 0 이면 merge를 수행한다.

- 각 줄의 첫째 숫자가 1이면 같은 parent를 갖는지 확인 후 결과를 출력한다.

 

#include <iostream>
#define VMAX 1000000 + 1

using namespace std;

int parent[VMAX]={0};
int n;

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

void merge(int sa, int sb){
  int a = getparent(sa);
  int b = getparent(sb);

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

bool sameparent(int sa, int sb){
  int a = getparent(sa);
  int b = getparent(sb);
  if(a==b) return true;
  else return false;
}


int main(){
  int m; cin >> n >> m;
  for(int i=0; i<=n; i++) parent[i]=i;

  for(int k,a,b,i=0; i<m; i++){
    scanf("%d %d %d", &k, &a, &b);
    if(k==0){
      merge(a,b);
    }else{
      bool p = sameparent(a,b);
      printf(p==true?"YES\n":"NO\n");
    }
  }
}

느낀점

몰랐던 알고리즘을 하나 하나 정복해 나가는 기분이 들어 뿌듯하다.