동일한 그룹인지를 확인할 때 유니온 파인드를 사용하자.

• 나동빈 님 블로그 참고 해서 공부함.
  https://blog.naver.com/ndb796/221230967614

정책

: 2개의 값을 비교해서 가장 낮은 값이 높은 vertex의 parent가 된다.

• GetParent를 하는 이유는 동일한 그룹에 소속시키기 위한 방법이다.

  Union(1, 2);
  Union(2, 3);

• -> 위의 2개의 코드를 생각하면
  parent[2] = 1이고, parent[3]는 2가 아니라,

  parent[3] = 1이 되어야 한다.

• 따라서 1번, 2번, 3번 parent는 동일한 값 1을 가지고 있기 때문에 같은 그룹에 있다고 할 수 있따.

parent 설정할 때

• 반드시 아래 코드처럼 해야 함.
  그래야 나의 vertex 값도 함께 갱신이 가능한 것이다.

• vertex[a] = GetParent 하지 않고
  return GetParent 하면 시간초과 발생한다.

int GetParent(int a)
{
    if (a == vertex[a])
        return a;
    else
        return vertex[a] = GetParent(vertex[a]);
}

경로 압축을 해야 하는 예시 코드

• GetParent 함수에서 갱신하지 않아서

1) vertex[3] 값이 0으로 갱신되지 않음.
2) 2번째 호출할 때도 cnt는 3이다.
=> 즉 한번 더 find 했을 때 시간복잡도가 갱신되지 않음을 확인할 수 있다.

• 경로 압축을 하면?
  : 한번의 호출로 인해 vertex[3] 이 갱신되었고,
  2번째 호출했을 때 cnt가 줄어든 것을 확인할 수 있다.
  

코드

#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;
#include <algorithm>
#include <map>


vector<int> vertex(11);

int GetParent(int a)
{
    if (a == vertex[a])
        return a;
    else
        return vertex[a] = GetParent(vertex[a]);
}

void Union(int a, int b)
{
    int aa = GetParent(a);
    int bb = GetParent(b);

    if (aa < bb)
        vertex[bb] = aa;
    else
        vertex[aa] = bb;
}



bool Check(int a, int b)
{
    int pA = GetParent(a);
    int pB = GetParent(b);

    if (pA == pB)
        return true;
    else
        return false;

}



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    
    for (int i = 1; i < 11; ++i)
    {
        vertex[i] = i;
    }

    Union(1, 2);
    Union(2, 3);
    Union(3, 4);
    Union(5, 6);
    Union(6, 7);
    Union(7, 8);

    cout << "1과 5가 연결되었나요 ? " << Check(1, 5) << endl; // => 0
    Union(1, 5);
    cout << "1과 5가 연결되었나요 ? " << Check(1, 5) << endl; // => 1 

}