BOJ(백준온라인저지)/11724/연결 요소의 개수

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

11724번: 연결 요소의 개수

그래프 자료형인 인접 리스트가 주어질 때 연결 요소의 개수를 묻는 문제이다.

DFS를 이용하면, 쉽게 풀 수 있는 문제다. 

문제 풀이 설계는,

1. 먼저 cin으로 adj list를 입력받기(adjacency list는 시작 - 끝, 끝 -시작 양 방향으로 우선 받아야 하므로 adj[u].push_back(v); adj[v].push_back(u); 두 개로 받는다.

2. 받은 adj list에 대해서 시작 노드를 한군데 찍고 dfs실행

3. 연결고리가 끊어진 그래프라면, dfs가 탐색을 종료하고(즉, 더 이상 재귀적으로 탐색을 하지 않는다.) 다시 추가 탐색한다. 

4. 재귀적으로 호출되는 dfs가 아닌 새로운 dfs가 시행될때마다 count를 +1 씩 더해준 다음 count를 리턴해주면, 원하는 연결 요소의 개수를 얻을 수 있다.

---

[구현 코드]

#include <vector>
#include <iostream>

using namespace std;
vector<vector<int>> adj;
vector<bool>visit;
int count;

void dfs(int here){
    visit[here] = true;
    for(int i = 0; i < adj[here].size(); i++){
        int there = adj[here][i];
        if(!visit[there]){
            dfs(there);
        }
    }
}

int main(){
    int N, M, u, v;
    cin>>N>>M;
    adj.resize(N+1);
    visit.resize(N+1, false);
    int count = 0; // 연결 요소의 개수를 위한 count integer 선언
    
    for(int i = 0; i < M; i++){
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    for(int i = 1 ; i <= N; i++){
        if(!visit[i]){
            count++;
            dfs(i);
        }
    }
    cout<<count;
    return 0;
}