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

문제

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

1717번: 집합의 표현

 

 

풀이

유니온 파인드(Union-Find) 알고리즘

유니온 파인드(Union-Find) 알고리즘

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

int find_parent(int a);
void union_parent(int a, int b);
static vector<int> parent;

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

  int n, m;
  cin >> n >> m;

  parent.resize(n + 1);
  for(int i = 0; i <= n; i++)
  {
    parent[i] = i;	// 대표 노드를 자기 자신으로 초기화하기
  }

  int check, a, b;
  for(int i = 0; i < m; i++)
  {
    cin >> check >> a >> b;
    if(check == 0)	
    {
      // 집합 합치기
      union_parent(a, b);
    }
    else if(check == 1)
    {
      // 두 원소가 같은 집합인지 확인
      if(find_parent(a) == find_parent(b))
      {
        cout << "YES" << "\n";
      }
      else
      {
        cout << "NO" << "\n";
      }
    }
  }

  return 0;
}

// find_parent 연산 : 대표 노드를 찾아서 반환
int find_parent(int a)
{
  if(a == parent[a])
  {
    return parent[a];
  }
  else
  {
    return parent[a] = find_parent(parent[a]);	// 재귀 함수 형태로 구현
  }
}

// union_parent 연산 : 바로 연결이 아닌 대표 노드끼리 연결함
void union_parent(int a, int b)
{
  // a와 b의 대표 노드 찾기
  a = find_parent(a);
  b = find_parent(b);

  // 두 원소의 대표 노드끼리 연결
  if(a < b)
  {
    parent[b] = a;
  }
  else if(a > b)
  {
    parent[a] = b;
  }
}