[1717번] 집합의 표현

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Disjoint-Set

2. Union Find :: http://www.crocus.co.kr/683

유니온 파인드에 대한 개념을 접목해 볼 수 있는 가장 기본적인 문제이다.

0을 입력 받을 시 두번째, 세번째 값을 union하여 묶어주고

1을 입력 받을 시 두번째, 세번째 값을 find하여 루트가 같은지 비교하면 된다.

위의 링크를 통해 유니온 파인드(Disjoint-Set)을 제대로 이해하고 문제에 접목해 보자.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87

#include <iostream> #include <cstdio>   #define swap(a,b){int t = a; a = b; b = t;}   using namespace std;   // parent[a] = b :: a의 부모는 b다 int parent[1000001]; int level[1000001];   int find(int u) {     // 루트 노드이면 return u     if (u == parent[u])         return u;       // 그 외에는 자신의 루트를 찾으러 간다.     return parent[u] = find(parent[u]); }   void merge(int u, int v) {     u = find(u);     v = find(v);       // 루트가 같다면 이미 같은 트리     if (u == v)         return;       // u가 v보다 더 깊은 트리라면 swap     if (level[u] > level[v])         swap(u, v); // 항상 u가 더 작은 트리가 되도록 한다.        // u의 루트가 v가 되도록     parent[u] = v;       // u와 v의 깊이가 같을 때 v의 깊이를 늘려준다.     if (level[u] == level[v])         ++level[v]; }   int main() {     int n, m;       scanf("%d %d", &n, &m);       // 초기에는 자신의 부모는 자기 자신     for (int i = 1; i <= n; i++)     {         parent[i] = i;         level[i] = 1;     }       while (m--)     {         int num;         scanf("%d", &num);           // u와 v를 union         if (num == 0)         {             int u, v;             scanf("%d %d", &u, &v);               merge(u, v);         }           // u와 v를 find 후 루트 비교         else if (num == 1)         {             int u, v;             scanf("%d %d", &u, &v);               u = find(u);             v = find(v);               u == v ? printf("YES\n") : printf("NO\n");         }     }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus