코딩테스트/백준
[백준] 11724번: 연결 요소의 개수
쪼르뚜
2024. 9. 9. 13:22
728x90
반응형
🔗 문제 링크
https://www.acmicpc.net/problem/11724
반응형
728x90
👩💻 코드
#include <iostream>
#include <vector>
using namespace std;
void DFS(int v, vector<bool> &visited, vector<vector<int>> &graph){
if (visited[v]){
return;
}
visited[v] = true;
for (int i : graph[v]){
if (visited[i] == false){
DFS(i, visited, graph);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
int M;
cin >> N >> M;
vector<vector<int>> graph(N+1);
vector<bool> visited(N+1, false);
for(int i=0; i<M; i++){
int u;
int v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
int count = 0;
for (int i=1; i<N+1; i++){
if(!visited[i]){
count++;
DFS(i, visited, graph);
}
}
cout << count <<"\n";
}
📝 풀이
Do it! 알고리즘 코딩테스트 - C++ 편 : 기출 유형 분석부터 문제 풀이 비법까지!를 참고하였습니다.
방향 없는 그래프의 연결 요소는 에지로 연결된 노드의 집합입니다.
즉, 한 번의 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 하나의 연결 요소로 판단합니다.
DFS는 재귀 함수로 연결 노드 중 방문하지 않은 노드가 남아 있을 때까지 탐색하도록 구현합니다.
728x90
반응형