11724_연결요소의 개수

연결요소의 정의는 다음과 같다. 

 A graph that is itself connected has exactly one component, consisting of the whole graph. Components are also sometimes called connected components. 

 

한 요소로 연결된 그래프는 전체 그래프를 구성하기 위한 요소로 있는데, 이 요소는 연결요소라고 불린다. 

쉽게 말해 연결된 그래프는 각각 하나의 연결 요소이다. 즉 이 그림에서는 3개의 연결 요소가 있다. 중요한 것은 점 한 개도 하나의 연결 요소라고 할 수 있다. 

나는 그 점들을 처리를 안해줘서 많은 실패를 하였다. 

저 연결요소를 찾는 것은 BFS를 이용해서 찾을 수 있다. 시작점에 대해 고민이 있었는데, 처음에는 점의 갯수 n을 이용하다가 n은 그저 점일 뿐이라서 set을 이용해 u, v를 넣어줬다. 그리고 중복처리 된 set에서 하나씩 빼주면서 처리해주었다. 

 

#include<iostream>
#include<vector>
#include<queue>
#include<set>
 
using namespace std;
 
bool check[1001];
vector<int> vg[1001];
 
int main(void){
    int n, m, u, v, ans;
    set<int> se;
    queue<int> q;
 
    cin >> n >> m;
    for(int i = 0; i < m;i++){
        cin >> u >> v;
        vg[u].push_back(v);vg[v].push_back(u);
        se.insert(u); se.insert(v);
    }
    ans = 0;
    if(n != 1)
    {
        for(auto it = se.begin(); it != se.end();it++){
 
            if(check[*it])
                continue;
            q.push(*it);check[*it] = true;
            while(q.size()){
                for(int j = 0; j < vg[q.front()].size();j++){
                    int tmp = vg[q.front()][j];
                    if(!check[tmp]){
                        q.push(tmp);
                        check[tmp] = true;
                    }
                }
                q.pop();
            }
            ans++;
        }
    }
    ans = ans + (n - se.size());
    cout << ans;
}