[C++/백준] 11724 연결요소의 개수

문제

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

입력

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

출력

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

DFS문제로, 방향없는 그래프인점을 고려해서 문제를 풀어야한다.

처음에 연결요소가 무슨 의미인지 알지 못해서 찾아봤었는데, 아래처럼 연결된 그래프들로 이루어진 요소들이 연결요소라고 할 수 있다. 아래의 연결요소는 2개로 이루어져있다.

연결요소의 예시

즉, 연결되어있는 덩어리를 확인하면 되는 문제.

 

#include <cstdio>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

vector<int> adj[1001];
int visited[1001];
int point, num;

void DFS(int a)
{
    visited[a] = 1;
    for (int i = 0; i < adj[a].size(); i++)
    {
        int next = adj[a][i];
        if (!visited[next])
            DFS(next);
    }
}

int main(void)
{
    scanf("%d %d", &point, &num);
    for (int i = 0; i < num; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int cnt = 0;

    for (int i = 1; i <= point; i++)
    {
        if (!visited[i])
        {
            DFS(i);
            cnt++;
        }
    }

    printf("%d", cnt);
}