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

문제:www.acmicpc.net/problem/11724 

11724번: 연결 요소의 개수

 

 

문제풀이

 

BFS/DFS를 이용하여 풀었다.

 

그래프의 연결 요소 즉, 서로 연결되지 않은 그래프들의 수를 구하는 문제이다.

 

연결 요소의 수를 구하는 방법으로 방문하지 않은 노드를 만나면 1을 카운트하고 해당 노드의 탐색을 진행했다. 

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

int N, M;
int visited[1001] = {0,}; //방문 여부
int link[1001][1001] = {0,}; //양방향 링크

void dfs(int n){ //깊이우선탐색
    visited[n] = 1;

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


void bfs(int n){ //너비우선탐색
    queue<int> q;
    q.push(n);

    while(!q.empty()){
        n = q.front();
        q.pop();

        for(int i=1; i<=N; i++){
            if(link[n][i] == 1 && !visited[i]){
                visited[i] = 1;
                q.push(i);
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin>>N>>M;

    for(int i=0; i<M; i++){
        int s, e;
        cin>>s>>e;
        link[s][e] = 1; //양방항 간선이므로 s->e 와 e->s 모두 1로 저장
        link[e][s] = 1;
    }

    int cnt = 0; //연결요소 수
    for(int i=1; i<=N; i++){
        if(!visited[i]){ //방문하지 않은 노드라면
            cnt++; //카운트하고
            bfs(i); //탐색
        }
     }

    cout<<cnt;

    return 0;
}

 

 

결과