[C++ / 백준 11724번] 연결 요소의 개수

문제

 

시행 착오

 

연결 요소 <-- 이게 무엇인지 이해를 하려고 검색했다.

 

연결 요소란 간단히 말해서 간선으로 이어진 정점들의 한 뭉탱이를 말한다.

1-3-5   2-4 
이렇게 연결 된 정점들이 있다면 연결 요소는 두 개인 것.

 

 

 

해결 방법

 

dfs 혹은 bfs 를 시행했을 때 한 번의 시행으로 전부 순회가 안 된다면 연결 요소가 두개 이상 있는 것이다. 두해당 알고리즘 시행 횟수만큼이 연결 요소의 개수가 된다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N, M, V;
vector<int> g[1001];
bool visited[1001] = { false };
queue<int> q;

int cnt = 0;

void dfs(int node)
{
    visited[node] = true;
    
    for (auto nextnode : g[node])
    {
        if (!visited[nextnode])
        {
            dfs(nextnode);
        }
    }
}

int main() {
    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 1; i <= N; i++)
    {
        sort(g[i].begin(), g[i].end());
    }


    for (int i = 1; i <= N; i++)
    {
        if (!visited[i])
        {

            cnt++;
            dfs(i);
        }
        else continue;
    }
    
    cout << cnt;

    return 0;
}