11724-연결 요소의 개수

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

그래프, DFS(Depth-First Search)에 관한 지식을 요구하는 문제입니다. 풀이는 다음과 같습니다.

 

1. 2차원 벡터를 사용하여 그래프의 연결관계를 표현합니다.

 

2. 먼저, 1번 노드에서 DFS 방법으로 인접 노드를 모두 탐색합니다. 탐색하며 각 노드에 대한 방문여부를 기록합니다. 1번 노드와 같은 연결 요소에 속하는 노드들은 모두 방문이 됩니다. 이는 연결 요소 하나를 탐색하는 과정으로 여기서 우선 연결 요소의 개수가 1이됩니다.

 

3. 그다음 2번 노드를 탐색하고 방문 여부를 확인합니다. 방문 여부가 True인 경우 1번 노드와 같은 연결 요소에 속해있다는 의미로 연결 요소의 개수를 증가시키지 않습니다. 방문 여부가 False인 경우 1번 노드와 다른 연결 요소에 속해있다는 의미로 인접 노드를 모두 탐색하고, 연결 요소의 개수를 1 증가시킵니다.

 

4. 위 과정을 3번, 4번, ..., N번 노드까지 반복합니다.

코드

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

int N;//정점의 개수
int M;//간선의 개수
vector<vector<int>> g;
vector<bool> visited;

void dfs(int node)
{
    for(int connected_node:g[node])
    {
        if(visited[connected_node]) continue;
        visited[connected_node] = true;
        dfs(connected_node);
    }
}

int main()
{
    //freopen("11724.txt", "r", stdin);
    cin >> N >> M;
    g.resize(N + 1);
    visited.resize(N + 1, false);

    for(int i = 0; i < M; i++)
    {
        int from;
        int to;
        
        cin >> from >> to;
        g[from].push_back(to);
        g[to].push_back(from);
    }

    int answer = 0;

    for(int node = 1; node <= N; node++)
    {
        if(visited[node]) continue;
        visited[node] = true;
        dfs(node);
        answer++;
    }

    cout << answer;
    return 0;
}