11724번-연결 요소의 개수

문제

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

11724번: 연결 요소의 개수

---

접근방법

1) 접근 사고

1.연결 요소의 개수를 구해주면 되기 때문에 방문한 노드 지점을 visited 배열을 사용해 체크해줍니다.

2. 방문한 지역은 visited를 사용해 제외해주었기 때문에 DFS 시도횟수의 의미가 전체 연결 개수의 의미를 의미하므로 DFS 시도 횟수를 출력해줍니다.

 

2) 시간 복잡도

O(V + E)

 

3) 실수

 

4) 배운점

 

5) PS

 

---

정답코드

#include <bits/stdc++.h>

using namespace std;

int n, m;
const int MAX = 1005;
vector<int> board[MAX];
bool visited[MAX];

void DFS(int cur){
    visited[cur] = true;
    for(auto next : board[cur]){
        if(!visited[next])
            DFS(next);
    }
}

int pro(){
    int count = 0;
    for(int i = 1; i <= n ; i++){
        if(!visited[i]){
            DFS(i);
            count++;
        }
    }
    return count;
}

void input(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int y, x;
        cin >> y >> x;
        board[y].push_back(x);
        board[x].push_back(y);
    }
}

int main(){
    input();
    cout << pro() << "\n";
}