백준 11724 - 연결 요소의 개수

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

// 백준 11724 - 연결 요소의 개수
// https://www.acmicpc.net/problem/11724

// 문제 설명
// 무방향 그래프에서 연결 요소(Connected Component)의 개수를 구하라

// 접근
// - 양방향 인접 리스트 구성
// - 모든 노드 순회 → 미방문 노드에서 DFS 시작할 때마다 ans++

#include <iostream>
#include <vector>
using namespace std;
#define endl '\n'

vector<int> v[1004];
bool visited[1004];

int dfs(int here)
{
    visited[here] = true;
    int cnt = 1;
    for (int i : v[here])
        if (!visited[i])
            cnt += dfs(i);
    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, a, b;
    cin >> n >> m;
    while (m--)
    {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (!visited[i])
        {
            dfs(i);
            ans++;
        }

    cout << ans << endl;
    return 0;
}

정리

• DFS를 새로 시작해야 하는 횟수 = 연결 요소의 수. 미방문 노드를 만날 때마다 ans++하면 된다.
• DFS 반환값은 이 문제에서 사용하지 않는다. 탐색 자체로 컴포넌트 내 노드를 전부 visited 처리하는 것이 목적이다.
• M = 0인 경우(간선 없음)에도 노드마다 DFS가 한 번씩 실행되므로 ans = N이 자연스럽게 나온다.

핵심 요약 — 연결 요소(서로 이어진 노드 묶음)의 개수는 “DFS를 새로 시작한 횟수”와 같다. 미방문 노드를 만날 때마다 카운트를 올리면 되고, 탐색의 목적은 반환값이 아니라 같은 컴포넌트를 전부 visited 처리하는 것 자체다.