Advertisement
newb_ie

Untitled

Oct 16th, 2021
230
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.88 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. const int maxN = 1e5 + 100;
  5. vector<int> adj[maxN];
  6. //~ adj[1] = {2,3}
  7. bool visited[maxN];
  8.  
  9. void dfs (int node) {
  10. //~ cout << "ENTERING node " << node << '\n';
  11. visited[node] = true;
  12. for (int i = 0; i < (int) adj[node].size(); ++i) {
  13. int child = adj[node][i];
  14. if (visited[child] == false) {
  15. dfs(child);
  16. }
  17. }
  18. //~ cout << "EXIT from " << node << '\n';
  19. }
  20.  
  21. int main () {
  22. ios::sync_with_stdio(false);
  23. cin.tie(nullptr);
  24. cout.tie(nullptr);
  25. int n, m;
  26. cin >> n >> m;
  27. for (int i = 1; i <= m; ++i) {
  28. int u,v; //u -> v and v -> u
  29. cin >> u >> v;
  30. adj[u].push_back(v);
  31. adj[v].push_back(u);
  32. }
  33. int cc = 0;
  34. for (int i = 1; i <= n; ++i) {
  35. if (visited[i] == false) {
  36. dfs(i);
  37. ++cc;
  38. }
  39. }
  40. cout << cc << '\n';
  41. }
  42.  
  43. //~ 7 6
  44. //~ 1 2
  45. //~ 1 3
  46. //~ 2 4
  47. //~ 2 5
  48. //~ 3 6
  49. //~ 3 7
  50.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement