Advertisement
Okorosso

модули

Jun 16th, 2021
799
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.91 KB | None | 0 0
  1. #include <fstream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6. vector<vector<int>> mat;
  7. int vertex, edges;
  8. vector<int> used(vertex);
  9.  
  10. bool dfs(int v) {
  11.     used[v] = 1;
  12.     for (int i = 0; i < mat[v].size(); i++) {
  13.         if (used[mat[v][i]] == 0) {
  14.             dfs(mat[v][i]);
  15.             used[v] = 2;
  16.         }
  17.     }
  18.     used[v] = 2;
  19.     return true;
  20. }
  21.  
  22.  
  23. int main() {
  24.     ifstream fin("input.txt");
  25.     ofstream fout("output.txt");
  26.  
  27.     fin >> vertex >> edges;
  28.     used.resize(vertex + 1);
  29.     mat.resize(vertex + 1, vector<int>());
  30.  
  31.     for (int i = 1; i < edges + 1; i++) {
  32.         int a, b;
  33.         fin >> a >> b;
  34.         mat[a].push_back(b);
  35.         mat[b].push_back(a);
  36.     }
  37.  
  38.     int count = 0;
  39.     for (int i = 1; i < used.size(); i++) {
  40.         if (used[i] == 0) {
  41.             dfs(i);
  42.             count++;
  43.         }
  44.     }
  45.    
  46.     fout << count;
  47.     return 0;
  48.  
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement