✅ 연결요소 ✅ DFS

문제

링크

풀이

연결요소란?

무방향 그래프에서 적어도 한 개 이상의 경로로 연결된 정점들로 구성된 종속 그래프를 의미한다.

-> 연결요소 2개

연결요소의 개수는 DFS나 BFS로 풀 수 있지만 본문제에서는 DFS로 풀었음

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

bool map[1001][1001];
bool visited[1001];
int N, M, sum=0;

void dfs(int u){
    visited[u] = true;

    for(int i=1;i<=N;i++){
        if (map[u][i] == true && visited[i] == false)
        {
            dfs(i);
        }
    }
}

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

    cin >> N >> M;

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

    for(int i=1;i<=N;i++){
        if(visited[i] == false){
            sum++;
            dfs(i);
        }
    }

    cout << sum << "\n";

    return 0;
}