[백준/c++] 11724번: 연결 요소의 개수

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

11724번: 연결 요소의 개수

 

문제 요약

 

방향없는 그래프, 연결 요소의 개수를 구하는 프로그램

→ 연결 요소란? 연결 그룹의 개수

 

 

범위

 

정점의 개수 N (1 ≤ N ≤ 1,000) 

간선의 개수 M (0 ≤ M ≤ N×(N-1)/2)

간선의 양 끝점 u, v (1 ≤ u, v ≤ N, u ≠ v)

 

 

---

 

 

DFS 를 이용해서 연결된 노드들을 방문했고, 방문한 적도 없고 연결되지도 않은(연결되지 않았으니 방문한 적이 없었을 것) 노드를 방문하면서 카운팅해준다.

 

#include <iostream>
#include <vector>
using namespace std;
int n, m, x, y, cnt=0;
bool visited[1002] = {false};
vector<int> graph[1002];

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

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

void solution(){
    for(int i=1; i<=n; i++){
        if(!visited[i]){ //방문하지 않은 정점
            cnt++;
            dfs(i);
        }
    }
    cout << cnt << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!