[백준] 11742 연결 요소의 개수

8492 단어 알고리즘bojboj

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

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

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

예제 입력 1
6 5
1 2
2 5
5 1
3 4
4 6
예제 출력 1
2
예제 입력 2
6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3
예제 출력 2
1

Concept

전형적인 dfs로 보여진다.
다른 시도를 해보려다 그냥 각각 노드의 이웃리스트를 만드는 것이 빠르게 먹힐 것 같았다.

Code

#include <iostream>
#include <deque>
#include <queue>
#include <string>
#include <string.h>
#include <vector>
using namespace std;

int n, m;
vector<vector<int>> arr(1001);
bool visited[1001];

void dfs(int here){
    visited[here]=true;
    for (int i=0; i<arr[here].size(); i++){
        if (!visited[arr[here][i]]){
            dfs(arr[here][i]);
        }
    }
    
}

void dfsAll(){
    int count=0;
    for (int i=1; i<=n; i++){ // 노드를 전체 탐색. 방문한 적 있다면 통과
        if (!visited[i]){
            dfs(i);
            count++;
        }
    }
    cout<<count;
}

int main(){
    memset(visited, false, sizeof(visited));
    
    cin>>n>>m;
    int inputA, inputB;
    for (int i=0; i<m; i++){ // 각각 노드의 이웃 리스트를 만들어준다.
        cin>>inputA>>inputB;
        arr[inputA].push_back(inputB);
        arr[inputB].push_back(inputA);
    }
    dfsAll();
}

Comment

풀고 보니 더더욱 dfs의 전형

좋은 웹페이지 즐겨찾기