문제

그래프의 연결 요소 개수 찾기

Idea

없음..

Code

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

#include <iostream>
#include <vector>

void DFS(const std::vector<std::vector<bool>>& graph, std::vector<bool>& visit, const int N, const int i){
    for (int j=1; j<=N; ++j){
        if ((!visit[j]) && (graph[i][j])){
            visit[j] = true;
            DFS(graph, visit, N, j);
        }
    }
}

int CountConnectedComp(const std::vector<std::vector<bool>>& graph, const int N){
    int answer = 0;
    std::vector<bool> visit(N+1, false);

    for (int i=1; i<=N; ++i){
        if (visit[i]){
            continue;
        }
        else{
            //not visited
            //  -> increase answer and DFS
            
            ++answer;

            visit[i] = true;
            DFS(graph, visit, N, i);
        }
    }

    return answer;
}

int main(){
    int M = 0;
    int N = 0;

    std::cin >> N >> M;

    std::vector<std::vector<bool>> graph(N+1, std::vector<bool>(N+1, false));
    for (int i=0; i<M; ++i){
        int from = 0;
        int to = 0;

        std::cin >> from >> to;
        graph[from][to] = true;
        graph[to][from] = true;
    }

    std::cout << CountConnectedComp(graph, N) << std::endl;

    return 0;
}