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

문제 : 링크텍스트

풀이 point

연결 요소란?
그래프의 덩어리를 말함. 트리로 치면 루트의 개수
그림을 보고 이해해보자.

undefined

자료구조 중 그래프를 활용한 문제이다. 그래프는 트리와 다르게 방문한 노드를 재방문 할 수 있기 때문에 visit 배열을 통해 방문 여부를 관리해야한다.

문제에서 첫번째로 방문할 노드를 정해주지 않았기 때문에 1 ~ N 만큼 반복해서 노드를 방문하고 처음 방문하는 노드가 있을 경우 연결 요소의 개수를 +1 해주면 된다.

풀이 순서

그래프 자료구조를 알아야 한다.
1. 입력 받기
2. 방문 알고리즘 선택 dfs or bfs
3. 1 ~ N까지 방문

코드

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

std::vector<int> graph[1001];
int N, M;
bool visit[1001];
int ans{0};

void dfs(int depth){
    visit[depth] = true;
    for(auto c : graph[depth]){
        if(visit[c]) continue;
        dfs(c);
    }
}

int main(){
    
    std::cin >> N >> M;
    for(int i{1}; i<=M; ++i){
        int a, b;
        std::cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i{1}; i<=N; ++i){
        if(visit[i]) continue;
        visit[i] = true;
        dfs(i);
        ++ans;
        
    }
    std::cout << ans;
    
    return 0;
}