11724 - 연결 요소의 개수

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

C++

1#include <bits/stdc++.h>
2using namespace std;
3
4void dfs(vector<vector<int>> &list, vector<bool> &visited, int v) {
5  visited[v] = true;
6
7  vector<int> neighbors = list[v];
8  for(int x : neighbors) {
9    if(!visited[x]) dfs(list, visited, x);
10  }
11}
12
13int main() {
14  int v, e;
15  scanf("%d %d", &v, &e);
16  vector<vector<int>> adjlist(v+1);
17  vector<bool> visited(v+1, false);
18
19  for(int i=0; i<e; ++i) {
20    int a, b;
21    scanf("%d %d", &a, &b);
22    adjlist[a].push_back(b);
23    adjlist[b].push_back(a);
24  }
25
26  int cnt = 0;
27  for(int i=1; i<=v; ++i) {
28    if(visited[i] == false) {
29      dfs(adjlist, visited, i);
30      ++cnt;
31    }
32  }
33
34  printf("%d\n", cnt);
35  return 0;
36}