코영방

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

연결 요소의 개수의 경우, DFS나 BFS를 공부를 공부한 후라면 간단하게 해결 가능하다.

모든 정점을 대상으로 방문한 적이 없는 정점이 있으면 그 정점을 기준으로 DFS 또는 BFS순회를 통해 방문했다는 체크를 해둔다. 그 후에도 아직 방문하지 않은 정점이 있다면 또 DFS나 BFS를 통해 순회하면서 방문했다는 체크를 하면 된다.

#include <bits/stdc++.h>
using namespace std;

int n, l;
vector <int> a[1005];
int visited[1005] = { 0, };

void dfs_l(int s) {
    int i;
    visited[s]++;
    for (i = 0; i < a[s].size(); i++){
        if (visited[a[s][i]] == 0){
            dfs_l(a[s][i]);
        }
    }

}

int main()
{
    int i, n1, n2, cnt = 0;
    scanf("%d %d", &n, &l);
    //간선 정보를 입력 받아 그래프 만들기
    for (i = 0; i < l; i++){
        scanf("%d %d", &n1, &n2);
        a[n1].push_back(n2);
        a[n2].push_back(n1);
    }
    
    //DFS 순회시에 인접 정점중에 정점번호가 작은 값부터 순회하기 위해 정렬
    //이번 문제에서는 굳이 없어도 됨.
    for (int i = 0; i < n; i++) {
        sort(a[i].begin(), a[i].end());
    }
    //방문하지 않은 정점을 발견하면 DFS순회함.
    //DFS가 호출되는 횟수가 연결요소의 개수가 됨.
    for (int i = 1; i <= n; i++){
        if (visited[i] == 0){
            dfs_l(i);
            cnt++;
        }
    }
    printf("%d", cnt);
    return 0;
}