[Silver 2] 11724번 연결 요소의 개수

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

11724번: 연결 요소의 개수

 

이 문제는 DFS를 통해 해결할 수 있다.

 

알고리즘은 다음과 같다.

• M개의 간선에 대해 정보를 받아 go, to와 to, go에 대해 그래프를 설정한다.
• N개의 정점에 대해 탐색을 시작하는데 방문하지 않았다면 DFS를 수행하고 연결 요소 수를 증가시킨다.
• DFS는 방문하지 않은 노드가 없을 때 까지 계속해서 진행한다.
• 모든 노드를 검사 했다면 연결 요소 수를 출력한다.

 

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

int N, M, cnt = 0;
int visited[1001] = { 0, };
int graph[1001][1001] = { 0, };

void dfs(int num)
{
    visited[num] = 1;
    for (int i = 1; i <= N; i++) {
        if (!visited[i]&&graph[num][i]) {
            dfs(i);
        }
    }
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int go, to;
        cin >> go >> to;
        graph[go][to] = 1; graph[to][go] = 1;
    }
    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            dfs(i);
            cnt++;
        }
    }
    cout << cnt << '\n';
}