[백준] 11724번: 연결 요소의 개수

---

🔗 문제 링크

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

---

반응형

728x90

👩‍💻 코드

#include <iostream>
#include <vector>
using namespace std;

void DFS(int v, vector<bool> &visited, vector<vector<int>> &graph){
    if (visited[v]){
        return;
    }
    
    visited[v] = true;
    
    for (int i : graph[v]){
        if (visited[i] == false){
            DFS(i, visited, graph);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    int M;
    cin >> N >> M;
    
    vector<vector<int>> graph(N+1);
    vector<bool> visited(N+1, false);
    
    for(int i=0; i<M; i++){
        int u;
        int v;
        cin >> u >> v;
        
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    int count = 0;
    
    for (int i=1; i<N+1; i++){
        if(!visited[i]){
            count++;
            DFS(i, visited, graph);
        }
    }
    
    cout << count <<"\n";
}

---

📝 풀이

Do it! 알고리즘 코딩테스트 - C++ 편 : 기출 유형 분석부터 문제 풀이 비법까지!를 참고하였습니다.

 

방향 없는 그래프의 연결 요소는 에지로 연결된 노드의 집합입니다.

즉, 한 번의 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 하나의 연결 요소로 판단합니다.

DFS는 재귀 함수로 연결 노드 중 방문하지 않은 노드가 남아 있을 때까지 탐색하도록 구현합니다.