HANCO
[백준] 연결요소의 개수 본문
안녕하세요
백준 연결요소의 개수 문제를 풀어보았습니다.
저는 DFS를 응용하여 풀었습니다.
#include<iostream>
#include<queue>
#include<vector>
#include<utility>
using namespace std;
vector<int> v[1001];
int N, M;
int visit[1001] = { 0, };
void dfs(int x) {
visit[x] = 1;
//해당 벡터배열의 크기만큼 탐색
for (int i = 0; i < v[x].size(); i++) {
int next = v[x][i];
//연결된 노드의 방문을 안했다면 그 노드를 재귀로 방문한다.
if (visit[next] == 0) {
dfs(next);
}
}
}
int main() {
cin >> N >> M;
int cnt = 0;
//해당 노드의 연결된 값들을 배열에 저장
for (int i = 0; i < M; i++) {
int a, b; cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
for (int i = 1; i <= N; i++) {
if (visit[i] == 0) {
dfs(i);
cnt++;
}
}
cout << cnt << '\n';
}
감사합니다.
'Algorithm > 백준알고리즘' 카테고리의 다른 글
[백준] 나이트의 이동 BFS (2) | 2020.05.10 |
---|---|
[백준] 로또 BFS (0) | 2020.05.10 |
[백준] 영역구하기 DFS (0) | 2020.05.09 |
[백준] 경로찾기 BFS (0) | 2020.05.09 |
[백준] 리모컨 [1107] (0) | 2016.12.20 |