[백준_11724] 연결 요소의 개수 c

문제

풀이과정

풀이

 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define EXIT_SUCCESS    0

int n, m, cnt = 0;

void dfs(bool** connection, bool* visited, int x)
{
    visited[x] = true;
    for (int i = 0; i < n; i++) {
        if (connection[x][i] && !visited[i]) {
            dfs(connection, visited, i);
        }
    }
}

int main ()
{   
    // 0) n, m 입력
    scanf("%d %d", &n, &m);
    
    // 1) connetion, visited 준비
    bool** connection = (bool **) malloc (sizeof(bool*) * n);
    for (int i = 0; i < n; i++) {
        connection[i] = (bool *) calloc (n, sizeof(bool));
    }
    bool* visited = (bool* ) calloc (n, sizeof(bool));

    // 2) connection 입력
    int u, v;
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        u--;
        v--;
        connection[u][v] = true;
        connection[v][u] = true;
    }
    
    // 3) dfs 시작
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            cnt++;
            dfs(connection, visited, i);
        }
    }

    // 4) 출력
    printf("%d", cnt);

    // 5) 메모리 해방
    for (int i = 0; i < n; i++) {
        free(connection[i]);
    }
    free(connection);
    free(visited);

    return EXIT_SUCCESS;
}