백준(BOJ) 11724번 연결요소의 개수

#include <cstdio>
#include <iostream>
#include <vector>
#include<cstring>
using namespace std;
 
 
vector<int> graph[1001];
bool chk[1001];
 
void dfs(int node) {
    chk[node] = true;
    for (int i = 0; i<graph[node].size(); i++) {
        int next = graph[node][i];
        if (chk[next] == false) {
            dfs(next);
        }
    }
}
 
int main() {
    int n, m;
    cin >> n >> m;
 
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
 
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
 
    int linkcnt = 0;
    memset(chk, false, sizeof(chk));
 
    for (int i = 1; i <= n; i++)
    {
        if (chk[i] == false)
        {
            dfs(i);
            linkcnt++;
        }
    }
 
    cout << linkcnt << endl;
 
    return 0;
}

연결요소(Connected Component)는 1개의 그래프 내에서 전부 이어져있지 않고 독립되어 떨어져있는 그래프안의 그래프라고 생각하시면 이해하기 수월할것입니다.

각 연결요소들은 서로 연결되어 있지 않고 독립적으로 존재하지만 하나의 그래프안에 속하는 정점,간선들의 집합들인것이죠. 

이 연결요소의 수를 파악하기 위해서는 탐색이 필요한데 dfs탐색을 통해 연결요소의 수를 구할수있습니다.

--------------------------------------------------------------------------------------------------------

 

 

이차원 vector를 이용하여 연결리스트 대신 간선의 정보를 저장하였습니다.

또한 체크용 배열 chk를 통해 탐색의 여부를 저장하였습니다. (memset함수로 초기화)