danielvitor23

Gincana

Apr 15th, 2023
1,031
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.59 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, m;
  5. vector<bool> visited;
  6. vector<vector<int>> gr;
  7.  
  8. void dfs(int u) {
  9.   visited[u] = true;
  10.   for (int to : gr[u]) {
  11.     if (!visited[to]) {
  12.       dfs(to);
  13.     }
  14.   }
  15. }
  16.  
  17. int main() {
  18.  
  19.   cin >> n >> m;
  20.  
  21.   visited.assign(n+1, false);
  22.   gr.assign(n+1, vector<int>());
  23.  
  24.   int a, b;
  25.   for (int i = 0; i < m; ++i) {
  26.     cin >> a >> b;
  27.  
  28.     gr[a].push_back(b);
  29.     gr[b].push_back(a);
  30.   }
  31.  
  32.   int cnt = 0;
  33.   for (int u = 1; u <= n; ++u) {
  34.     if (!visited[u]) {
  35.       ++cnt;
  36.       dfs(u);
  37.     }
  38.   }
  39.  
  40.   cout << cnt << '\n';
  41. }
Advertisement
Add Comment
Please, Sign In to add comment