[알고리즘] [14][백준_11724] - 연결 요소의 개수

 

---

1. 문제이해

주어진 정점과 간선으로 그래프를 만들었을때 서로 이어져있는 그래프의 집합이 몇개인지를 구하는 문제이다.

 

---

2. 알고리즘 전략

문제 자체는 간단하지마 한가지 고려해야 할 사항은 그래프를 표현할때 다음과 같이

 

1. 2차원 배열로 나타낼수도 있고

2. 벡터를 사용하여 정점과 그 간선의 연결상태만 

 

나타낼 수 있다.

 

 

위 문제의 경우 정점의 개수가 최대 1000개 이므로 배열의 크기는 1000*1000*4byte(int)로 약 400MB정도 되어 문제에서의 최대 메모리인 512MB보다는 작지만, 아마 프로그램 실행을 위한 기본 메모리값으로 인해, 최대 메모리인 512MB를 넘어 메모리초과가 발생한다.

 

따라서 벡터를 이용해서 각 정점들과 이어진 정점들만 넣어 구현하고,

1차원 배열을 만들어 방문한 정점은 체크해두면서 그래프 순회를 하면된다.

 

 

#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int t,m,n,k;
int Count = 0;
vector<vector<int> > v;
int graph[1001];
// graph[x] = 1 -> 아직 방문 안한 상태
// graph[x] = 0 -> 방문 한 상태

void sub_loop(int now){
    for(int i=0;i<v[now].size();i++){
        if(graph[v[now][i]] == 1){
            graph[v[now][i]] = 0;
            sub_loop(v[now][i]);
        }
    }
}

void main_loop(){
    for(int i=0;i<n;i++){
        if(graph[i] == 1){
            Count++;
            graph[i] = 0;
            sub_loop(i);
        }
    }
}

int main(){
    int tmp1, tmp2;
    cin >> n;
    cin >> m;
    for(int i=0;i<n;i++){
        v.push_back(vector<int>());
        graph[i] = 1;
    }

    for(int i=0;i<m;i++){
        cin >> tmp1;
        cin >> tmp2;
        v[tmp1-1].push_back(tmp2-1);
        v[tmp2-1].push_back(tmp1-1);
    }

    main_loop();
    cout << Count;
}