BOJ)11724 연결 요소의 개수

문제 : https://www.acmicpc.net/problem/11724

graph를 행렬화 시켜서 bfs를 돌려보았더니, 시간이 오래걸리는 것이 느껴졌다.

이전, 1260 문제 풀이(http://rhkdrmfh.tistory.com/30) 중 두번째의 방법과 유사하게 풀이하였다.

연결 요소가 N개 존재할 때, BFS 혹은 DFS는 N번 시행되어야한다.

for (int i = 1; i <= vertex_num; i++) { if (visited[i] == false) { BFS(i); cnt++; } }

만약, 첫 탐색을 실시하였음에도 방문되지 않은 vertex가 있다면, 그 vertex는 탐색되어진 곳과는 연결되어져 있지 않는 즉, 다른 연결요소의 vertex 중 하나가 된다.

#include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <cstring> using namespace std; int vertex_num, edge_num; vector <int> graph[1001]; bool visited[1001] = { false }; queue <int> BFS_NUM; void BFS(int start) { visited[start] = true; BFS_NUM.push(start); while (BFS_NUM.empty() == false) { int now_position = BFS_NUM.front(); BFS_NUM.pop(); for (int i = 0; i < graph[now_position].size(); i++) { int next_position = graph[now_position][i]; if (visited[next_position] == false) { visited[next_position] = true; BFS_NUM.push(next_position); } } } } int main() { int vertex_left, vertex_right; int cnt = 0; cin >> vertex_num >> edge_num; for (int i = 0; i < edge_num; i++) { cin >> vertex_left >> vertex_right; graph[vertex_left].push_back(vertex_right); graph[vertex_right].push_back(vertex_left); } for (int i = 1; i <= vertex_num; i++) { if (visited[i] == false) { BFS(i); cnt++; } } cout << cnt; }