Advertisement
deushiro

Untitled

Jan 14th, 2020
228
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.17 KB | None | 0 0
  1. #include <cmath>
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <string>
  6. #include <set>
  7. #include <map>
  8. #include <list>
  9. #include <time.h>
  10. #include <math.h>
  11. #include <random>
  12. #include <deque>
  13. #include <queue>
  14. #include <cassert>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. #include <iomanip>
  18. #include <bitset>
  19. #include <sstream>
  20. #include <chrono>
  21. #include <cstring>
  22. #include <fstream>
  23.  
  24. using namespace std;
  25.  
  26.  
  27. typedef long long ll;
  28.  
  29. const ll mod = 1e9 + 7;
  30.  
  31. vector<vector<int>> a;
  32. vector<bool> flag;
  33. vector<vector<int>> c;
  34.  
  35. void dfs(int v){
  36.     flag[v] = true;
  37.     c.back().push_back(v + 1);
  38.     for(int u : a[v]){
  39.         if(!flag[u])
  40.             dfs(u);
  41.     }
  42. }
  43.  
  44. int main()
  45. {
  46.     fstream in;
  47.     in.open("input.txt", ios::out);
  48.     int n, m;
  49.     in >> n >> m;
  50.     a.resize(n);
  51.     flag.resize(n);
  52.     for(int i = 0; i < m; ++i){
  53.         int v, u;
  54.         cin >> v >> u;
  55.         --v; --u;
  56.         a[v].push_back(u);
  57.         a[u].push_back(v);
  58.     }
  59.     for(int i = 0; i < n; ++i){
  60.         if(!flag[i]){
  61.             c.push_back({});
  62.             dfs(i);
  63.         }
  64.     }
  65.     cout << c.size() << "\n";
  66.    
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement