연결 요소의 개수 11724

문제

접근 방법

문제 자체는 간단하게 적혀있다.
그래서 연결 요소가 무엇인지 모르면 이해를 못 한다.
나는 몰라서 의미만 알아보고 왔다.
연결 요소란 여태까지 영역이라고 불렀던 것이다.
즉 영역이 몇 개인지 구하면 되는 문제이다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, M, ret = 0;
    cin >> N >> M;
    vector<vector<int>> map(N + 1);
    vector<bool> visted(N + 1);
    queue<int> bfs;
    for (int i = 0; i < M; ++i)
    {
        int start, end;
        cin >> start >> end;
        map[start].push_back(end);
        map[end].push_back(start);
    }
    for (int i = 1; i <= N; ++i)
    {
        if (visted[i])
            continue;
        visted[i] = true;
        ++ret;
        bfs.push(i);
        while (!bfs.empty())
        {
            int cur = bfs.front();
            bfs.pop();
            for (int j : map[cur])
            {
                if (visted[j])
                    continue;
                visted[j] = true;
                bfs.push(j);
            }
        }
    }
    cout << ret;
}

풀이

BFS 또는 DFS로 연결된 부분을 모두 탐색하며 방문했음을 표시하면 1개의 영역을 완료한 것이다.
남은 영역들 또한 방문하지 않았다면 같은 방식으로 탐색해주면 된다.