<백준> 11724번 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

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

문제 해결 과정:

-dfs를 사용

-연결 요소의 개수는 요소 가운데 요소 내 모든 노드쌍에 대해 경로가 존재하는 부그래프 s를 g의 연결요소(conected component)라고 한다

- 모든 정점에 대해서 dfs를 돌리고 새로운 그래프가 발견 될때마다 카운트를 한다.

#include<iostream>
#include<stack>
using namespace std;
 
int map[1002][1002] = {0,};
int visited[1002] = { 0, };
int N, M;
int cnt = 0;
 
void dfs(int root) {
    if (visited[root]) {
        return;
    }
    
    cnt++;
    stack<int> s;
    s.push(root);
    visited[root] = 1;
    while (!s.empty())
    {
        int temp = s.top();
        s.pop();
        for (int i = 1; i <= N; i++) {
            if (map[temp][i] && !visited[i]) {
                visited[i] = 1;
                s.push(i);
            }
        }
    }
}
 
int main() {
    scanf_s("%d %d", &N, &M);
    for (int i = 0; i < M; i++) {
        int u,v;
        scanf_s("%d %d", &u, &v);
        map[u][v] = map[v][u] = 1;
    }
 
    for (int i = 1; i <= N; i++) {
        dfs(i);
    }
    
    printf("%d\n", cnt);
 
}