BOJ 1717: 집합의 표현

배웠던 Union-Find를 복습하기 위해 풀어봤습니다.

동빈나 유튜버 님이 구현한 함수를 최대한 이용해보려고 했습니다.

3개 함수(getParent, unionParent, findParent) 모두 이용하고 인자에 부모 노드 배열을 전달하는 방식으로 구현했더니 시간초과 에러가 발생했습니다.

시간초과 문제를 해결하기 위해 1) 함수 하나를 줄이고 2) 인자를 통해 부모 노드 배열을 전달하는 대신 전역변수로 설정하니 통과했습니다. (getParent, unionParent 사용)

 

시간 초과 됐던 코드

#include <iostream>
using namespace std;

int n, m;

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

void unionParent(int parent[], int a, int b) {
  a = getParent(parent, a);
  b = getParent(parent, b);

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

int findParent(int parent[], int a, int b) {
  a = getParent(parent, a);
  b = getParent(parent, b);
  if(a==b) return 1;
  return 0;
}

int main(void) {
  int parent[1000001];
  cin >> n >> m;
  for(int i = 0; i <= n; i++) parent[i] = i;
  for(int i = 0; i < m; i++) {
    int op, a, b;
    cin >> op >> a >> b;
    if(op == 0) {
      unionParent(parent, a, b);
    } else {
      if(findParent(parent, a, b) == 1) cout << "YES\n";
      else cout << "NO\n";
    }
  }
  return 0;
}

 

 

통과한 코드

#include <iostream>
using namespace std;

int parent[1000001];
int n, m;

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

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

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

int main(void) {
  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  cin >> n >> m;
  for(int i = 0; i <= n; i++) parent[i] = i;
  for(int i = 0; i < m; i++) {
    int op, a, b;
    cin >> op >> a >> b;
    if(op == 0) {
      unionParent(a, b);
    } else {
      if(getParent(a) == getParent(b)) cout << "YES\n";
      else cout << "NO\n";
    }
  }
  return 0;
}

 

 

 

Reference

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

1717번: 집합의 표현