BOJ - 11724 - 연결 요소의 개수
연결요소란 서로 연결되어 있는 그래프를 말한다. 따라서 연결되어 있지 않은 그래프의 개수를 구하는 문제이다.
그래프를 순회하면서 방문표시가 되어있지 않은 정점을 표시하면 되는 간단한 문제이다. 이 문제의 포인트는 방향이 없는 그래프라는 것..! 양 끝 점이 주어졌을 때 양쪽을 모두 연결 해준다면 간단하게 해결할 수 있다.
또 주의할 것은 dfs를 들어가자마자 방문을 체크하고 return 하는 것이 아니라
해당 정점에 연결되어 있는 점들을 확인할 때 방문을 체크해야 한다.
풀이보기
```c++
#include<iostream>
#include<vector>
using namespace std;
vector<vector <int>> node;
bool visited[1001];
int N, M, ans;
void dfs(int v) {
// 방문했으면 return;
if (!visited[v]) return;
visited[v] = true;
for(int i=0; i<vector[v].size(); i++) {
dfs(vector[v][i]);
}
}
// 1부터 시작하기 위해 N+1까지
node.resize(N+1);
int main(void) {
scanf("%d %d", &N, &M);
// M개 간선 입력받기
for(int i=0; i<M; i++) {
int a, b;
scanf("%d %d", &a, &b);
vector[a].push_back(b);
vector[b].push_back(a);
}
// 1~N까지 정점 순회
for(int i=1; i<N+1; i++) {
if(!visited[i]) dfs(i); ans++;
}
}
```
처음에 그래프를 양쪽에 연결하지 않아서 한참을 해맸던 문제다.