유니온 파인드

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

1717번: 집합의 표현

유니온 파인드 3가지

외워야 한다!! 이 두 함수를 커스텀하는 것이다.

1. int find(int a)

2. void unionfunc(int a, int b)

3. for (int i = 0; i <= n; i++)

   parent[i] = i;

 

find 연산 재귀 이유?

대표 노드(조상)에 도달하면

재귀를 빠져나오며 거치는 모든 값들을

대표 노드값으로 변경한다.

 

<소스 코드>

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<int> parent;
 
// find 연산: 대표 노드를 찾아서 반환
int find(int a)
{
    if (a == parent[a])
        return a;
    else
        return parent[a] = find(parent[a]);
}
 
// union 연산 : 바로 연결이 아닌 대표 노드끼리 연결
void unionfunc(int a, int b)
{
    a = find(a);
    b = find(b);
 
    if (a != b)
        parent[b] = a;
}
 
// 두 원소가 같은 집합인지 확인
bool checkSame(int a, int b)
{
    a = find(a);
    b = find(b);
 
    if (a == b)
        return true;
 
    return false;
}
 
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;
 
    for (int i = 0; i < m; i++)
    {
        int question, a, b;
        cin >> question >> a >> b;
 
        if (question == 0)
            unionfunc(a, b);
        else
        {
            if (checkSame(a, b)) 
            {
                cout << "YES" << '\n';
            }
            else
            {
                cout << "NO" << '\n';
            }
        }
    }
 
    return 0;
}

이 문제는 집합의 개수를 카운트해야한다.

 visited[] 배열 만들어서

for (int i = 1; i <= n; i++) {
    int root = find(i);
        if (!visited[root]) {
            visited[root] = true;
            ans++;
    }            
}

 

이렇게 해주면 끝이다.