(매일 BOJ) C++ 11724번 연결 요소의 개수

이번 문제는 11724번 연결 요소의 개수다.

문제 개요

그래프 이론에서 Connected Component란, 서로 연결되어 있는 정점들의 집합을 의미한다
백준 11724번에서는 주어진 무방향 그래프의 연결 요소 개수를 구해야 함

 

문제 조건

• 입력
  1. 첫 줄에 정점의 개수 N, 간선의 개수 M
  2. 다음 M개의 줄에는 간선 정보 u v (u와 v는 연결된 정점)
  • 정점 번호는 1부터 N까지
• 출력
  • 그래프의 연결 요소 개수

접근법

1. 그래프 저장 방식
   • vector<vector<int>>를 이용한 인접 리스트 방식
2. 방문 체크
   • vector<bool>로 방문한 정점을 기록
3. DFS 수행
   • 방문하지 않은 노드에서 DFS 시작 → 해당 노드와 연결된 모든 노드 방문
   • DFS가 한 번 완료될 때마다 연결 요소 개수 +1
4. 결과 출력

작성코드

#include <bits/stdc++.h>
using namespace std;

void DFS (int i,vector<vector<int>> & vertex,vector<bool> & visited,int& result);

int main(void){
    ios::sync_with_stdio(false); cin.tie(0);
    int N,M;
    cin >> N >> M;
    vector<vector<int>> vertex(N+1);
    for(int i = 1; i <= M; i++){
        int a,b;
        cin >> a >> b;
        vertex[a].push_back(b);
        vertex[b].push_back(a);
    }

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

    vector<bool> visited(N+1,false);
    int result = 0;

    for(int i = 1; i <= N; i++){
        if(!visited[i]){
           DFS(i,vertex,visited,result);
           result += 1;
        }
    }

    cout << result;


}

void DFS (int i,vector<vector<int>> & vertex,vector<bool> & visited,int& result){
    visited[i] = true;

    for(int next : vertex[i]){
        if(!visited[next]){
            DFS(next,vertex,visited,result);
        }
    }
}