백준 연결요소의 갯수 11724

Disjoint-Set / 문제로 쉽게 연결되는 고리와 어느 지점에서 그 부모를 찾을수 있는 자료구조를 연습 

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

#include <stdio.h>
#include <iostream> 
#include <memory.h>
 
 
using namespace std;
int parent[1000005];
int ans = 0;
int arr[1000005] = { 0, };
 
// 부모를 찾아주는 함수 
int find(int x){
 
    int root = -1;
 
    if (parent[x] == x)
        root = x;
    else
        root = find(parent[x]);
 
    parent[x] = root;
    
    return root;
    
 
}
 
//b를 a와 연결시켜주는 함수 //
void link(int a, int b) {
 
    //결국 여기서 .. 부모를 찾아 줌.. 
 
    int pa = find(a);
    int pb = find(b);
 
 
    if (pa != pb)
        arr[pa] += arr[pb];
    else
        return;
 
 
    parent[pb] = pa;
 
}
 
int main() {
 
 
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    int N, M;
    int a, b;
 
//    freopen("input.txt", "r", stdin); setbuf(stdout, NULL);
 
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++){
        parent[i] = i;
    }
 
 
 
    for (int i = 0; i < M; i++){
        cin >> a >> b;
        link(a, b);
    }
 
 
    ans = N;
 
 
    for (int i = 1; i <= N; i++){
 
        //결국 1번부터 N 번까지 부모를 찾아서 i 와 같으면 --> 그경우는 부모와 본인이 같으므로 
        //연결 요소는 아님 즉 어디에 연관되어져있따.
 
        
        if (find(i) != i) ans--;
 
    }
 
    cout << ans << "\n";
 
    return 0;
}