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

11724번: 연결 요소의 개수 (acmicpc.net)

11724번: 연결 요소의 개수

---

저번 dfs, bfs 문제는 인접행렬을 통해서 했었는데, 인접 리스트가 더 좋은 것 같아서 이번에는 벡터를 이용한 인접 리스트를 이용해서 풀어볼 것이다! 

 

벡터를 이용한 인접 리스트

한 노드에서 인접한 정점들을 모두 벡터로 연결시킨다.

vector<int> v[node개수+1];
v[시작 노드].push_back(인접한 노드);

 

vector<int> v[4];
v[1].push_back(2);
v[1].push_back(3);
v[1].push_back(4);
v[2].push_back(3);

 

연결된 노드를 확인하는 법

for(int i=0; i<v[현재노드].size(); i++){
	int next_node = v[현재노드][i];
}

---

이해하기

 

연결 요소를 구하기 위해서는 먼저 그래프를 인접 리스트를 통해 저장한다. 첫번째 노드부터 DFS나 BFS를 사용해서 탐색을 진행하는 데, 탐색이 진행될때마다 count를 증가시켜서 탐색의 횟수를 세어주면 연결 요소의 개수를 구할 수 있다. 

 

-- 겪었던 문제

"방향 없는 그래프가 주어졌을 때, " 라는 조건이 제시되어 있다. 

따라서 벡터에 주어진 간선들을 저장할 때, 방향이 있는 그래프는 한쪽 방향만 저장해도 되지만 이 문제의 경우 양쪽 방향을 모두 저장해줘야한다. 

    for(int i=0; i<m; i++){
        cin >> a >> b;
        v[a].push_back(b);
        //인접한 노드 두 쪽 모두 해줘야함! (무방향 그래프)
        v[b].push_back(a);
    }

 

위와 같이 수정해주니 맞았다!

 

---

최종 코드

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

vector<int> v[1001];
int visited[1001]={0,};
int count = 0;

void dfs(int n){
    visited[n] = 1;
    for(int i=0; i<v[n].size(); i++) {
        int x = v[n][i];
        if(visited[x] == 0) dfs(x);
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    
    int a, b;
    for(int i=0; i<m; i++){
        cin >> a >> b;
        v[a].push_back(b);
        //인접한 노드 두 쪽 모두 해줘야함! (무방향 그래프)
        v[b].push_back(a);
    }
    
    for(int i=1; i<=n; i++){
        if(visited[i] == 0){
            dfs(i);
            count++;
        }
    }
    cout << count << "\n";
    return 0;
}