백준 11724 - 연결 요소의 개수

문제 설명

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 방향이 없는 그래프 간선 정보가 주어졌을 때 컴포넌트의 개수를 구하는 것이다.

 

해당 문제는 Bfs, Dfs 로도 충분히 풀 수 있다.

하지만, 연결 관계만 판정하면 되기 때문에 유니온 파인드를 이용했다.

 

int FindRoot(int x)
{
    if (root[x] == x) return x;
    return root[x] = FindRoot(root[x]);
}

void Union(int a, int b)
{
    a = FindRoot(a);
    b = FindRoot(b);

    //빠른 순서 정렬
    if (a > b) swap(a, b);
    root[b] = a;
}

Find의 경우에는 경로 압축을 통해 시간을 최소화하였다.

Union의 경우 자식의 개수나 특정 기준을 통해 root를 정할 수 있지만 해당 문제는 단순히 연결 관리만 하면 되기 때문에 숫자가 작은 노드가 root가 되도록 만들었다.

 

위 함수를 통해 연결 구조를 만들었다면 root의 개수를 세면 된다.

root의 개수를 세는 방법은 모든 노드를 다시 Find 한 결과가 자신과 같다면 해당 노드는 root노드이다.

int ans = 0;
for (int i = 1; i <= N; i++)
{
    if (FindRoot(i) == i) ans++;
}

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N, M;
vector<int> root;

int FindRoot(int x)
{
    if (root[x] == x) return x;
    return root[x] = FindRoot(root[x]);
}

void Union(int a, int b)
{
    a = FindRoot(a);
    b = FindRoot(b);

    //빠른 순서 정렬
    if (a > b) swap(a, b);
    root[b] = a;
}

int main() 
{
    INPUT_OPTIMIZE;

    cin >> N >> M;

    root.resize(N+1);
    for (int i = 1; i <= N; i++)
    {
        root[i] = i;
    }

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

    int ans = 0;
    for (int i = 1; i <= N; i++)
    {
        if (FindRoot(i) == i) ans++;
    }

    cout << ans;

    return 0;
}

---