BOJ - 11724 - 연결 요소의 개수

문제

11724번: 연결 요소의 개수

문제

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

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

구현

#include <iostream>
#include <vector>

using namespace std;

// map
vector<int> map[1004];
int visited[1004];
int n, m;
int cnt = 0;

void dfs(int idx)
{
    visited[idx] = 1;
    for(auto &el : map[idx])
    {
        int index = el;
        if(!visited[index])
            dfs(el);
    }
}

int main()
{
    cin >> n >> m;
    int u, v;
    // 연결 리스트 생성 
    for(int i=0; i < m; i++)
    {
        cin >> u >> v;
        map[u].push_back(v);
        map[v].push_back(u);
    }
    // 완전 탐색, 방문하지 않았더라면 == 간선++
    for (int i = 1; i <= n; i++) 
        if (!visited[i])
        {
            cnt++;
            dfs(i);
        }
    
    cout << cnt;
    return 0;
}

SOL

1. 연결 리스트 생성
2. 탐색 후 방문하지 않았더라면 cnt++

Reference & 다른 PS 모음집

GitHub - ggh-png/PS: 2021.01.11 start

BFS 너비 우선 탐색

DFS 깊이 우선 탐색