[BaekJoon] 11724번 : 연결

• 이 글은 c++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

• 그래프를 구현할 수 있는지 확인하는 문제로 인접행렬이나 인접리스트를 통해 표현할 수 있습니다.
• 이 문제 같은 경우는 인접행렬보다 인접리스트로 풀 경우 시간복잡도가 낮습니다. O(N2) < O(N+M)
• 그래프를 표현한 후 BFS 탐색을 통해 구현할 수 있습니다.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

vector<int> vec[1005];


int main(){
    int n,m;
    cin>>n>>m;
    
    bool visit[1005];
    fill(visit, visit+1005, false);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
   
    int cnt = 0;
    for(int i=1;i<=n;i++){
        if(!visit[i]){
            visit[i] = true;
            cnt++;
            
            queue<int> q;
            q.push(i);
            
            while(!q.empty()){
                int cur = q.front();
                q.pop();

                for(int j=0;j<vec[cur].size();j++){
                    int nxt = vec[cur][j];
                    if(!visit[nxt]){
                        q.push(nxt);
                        visit[nxt] = true;
                    }
                }
            }
        }
    }
    cout<<cnt;
}

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.