백준11724_연결 요소의 개수_bfs

-문제-

 

 

-문제 접근-

무방향 그래프에서 첫 줄에 정점의 개수 N 과 간선의 개수 M을 받고 두번째 줄 부터 간선의 개수 만큼 간선의 양 끝점 u,v를 받으며 

연결 요소의 개수를 구하는 문제이다. 

 

연결 요소의 개수라는 말이 무슨 말인가 싶을 수 있는데 한마디로 서로 연결이 되어있지 않은 개별의 그래프의 개수를 의미한다고 이해하면 좋을 것 같다.

 

-문제 풀이-

 

변수

노드와 간선의 관계를 저장하기위해 vector를 사용하여 adj를 선언하고 방문여부를 확인 하여야 하므로 vis를 선언한다.

(크기는 문제의 조건에 맞게)

 

main

입력값 N과 M을 받아주어야 하며 그 다음 줄 부터 간선의 끝점 u, v를 받아서 연결을 해줘야 되므로 vector adj에 push_back을 하여 간선 처리를 해준다.

int cnt 개별적 그래프들의 카운트 해주기 위해서 선언하고 for문으로 노드 전체를 돌리면서 vis에 방문 되지 않은 것만 bfs를 돌려 연결 요소들의 개수를 카운팅해주면 문제의 출력 값이 된다.

 

bfs

일반적인 정석 bfs이기에 설명 생략

 

 

 

 

-전체 코드-

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
vector<int> adj[1001];
bool vis[1001];

void bfs( int s){
    queue<int> q;
    q.push(s);
    vis[s] = true;
    
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        
        for(auto nxt : adj[cur]){
            if(vis[nxt]) continue;
            q.push(nxt);
            vis[nxt] = true;
        }
    }
   
}

int main(){
    int N, M;
    cin >> N >> M;
    
    while(M--){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        
    }
    
    
    
    int cnt = 0;
    
    for(int i = 1;i <= N; i++){
        if(vis[i]) continue;
        bfs(i);
        ++cnt;
    }
    
    cout << cnt <<"\n";
    return 0;
    
}