백준 / 2606 / 바이러스 / C++ / 알고리즘 문제풀이 (Union - Find)

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

2606번: 바이러스

 

2606번 유니온 파인드 사용 풀이입니다.

문제를 풀고 정답으로 채점받는 것 까지는 괜찮았는데, 헷갈리는 개념들이 있어서 백준 게시판에 질문을 올렸고

다행히도 답변을 받았습니다 ! 링크 올려드리겠습니다. (https://www.acmicpc.net/board/view/104773)

아래는 유니온 파인드로 푼 코드입니다.

 

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int N, M;
int parent[101];
 
int Find(int x)
{
    if (parent[x] == x)
        return x;
    else
        return Find(parent[x]);
}
 
void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
 
    if (x == y)
        return;
    else if (x > y)
        parent[x] = y;
    else
        parent[y] = x;
        
}
 
int main()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        parent[i] = i;
    }
 
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        Union(a, b);
    }
 
    int check = Find(1);
    int ans = 0;
 
    for (int i = 2; i <=N; i++)
    {
        if (Find(i) == check)
            ans++;
    }
 
    cout << ans << endl;
 
    return 0;
 
}