백준 2606번 Union-Find 풀이

---

백준 2606번

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. ···

#include <iostream>
using namespace std;

int parent[110];

int getParent(int x)
{
    if (parent[x] == x) return x;
    return parent[x] = getParent(parent[x]);
}

void unionParent(int a, int b)
{
    a = getParent(a);
    b = getParent(b);

    if (a < b)
        parent[b] = a;
    else
        parent[a] = b;
}

bool findParent(int a, int b)
{
    a = getParent(a);
    b = getParent(b);

    if (a == b)
        return true;
    return false;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int computer;
    cin >> computer;
    for (int i = 1; i <= computer; i++)
    {
        parent[i] = i;
    }

    int a, b, group;
    cin >> group;

    for (int i = 0; i < group; i++)
    {
        cin >> a >> b;
        unionParent(a, b);
    }

    int result = 0;
    for (int i = 2; i <= computer; i++)
    {
        if (findParent(parent[i], 1))
            result++;
    }

    cout << result << "\n";

    return 0;
}