Advertisement
Guest User

Untitled

a guest
Mar 18th, 2019
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.88 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<fstream>
  4.  
  5. using namespace std;
  6.  
  7.  
  8. //алгоритм обхода в глубину, суть его в том, что мы начнаем с какой-то вершинкой и далее переходим во все вершины смежные с ней
  9. // и таким образом он проходит по всему графу и помечает вершины в массиве used которые посетил как true, чтобы второй раз в них не заходить
  10.  
  11. void DFS(int v, vector<vector<int>> &e,vector<bool> &used)
  12. {
  13. used[v] = true;
  14. for (int i = 0; i < e[v].size(); i++)
  15. {
  16. int tek = e[v][i];
  17. if (!used[tek])
  18. DFS(tek, e, used);
  19. }
  20.  
  21. }
  22.  
  23. // будем исходить из определения - компонентой связанности называется такое множество вершин, что мы из каждой можем добраться в каждую
  24. // DFS он проходит по всем вершинам до которых есть путь из вершины i , тем самым он за один проход выделить компненту связанности
  25. // далее нам нужно запуститься из всех вершин до которых DFS не смог дойти в первый раз и т.д.
  26.  
  27. int CountComponents(vector<vector<int>> &e, vector<bool> &used, int n)
  28. {
  29. int count = 0;
  30.  
  31. for (int i = 0; i < n; i++) // идем по всем вершинам и пооочереди запускаемся из них DFS'ом при этом проверяя, посещали ли мы ее уже
  32. { // если посещали, то значит она относится к какой-то компоненте связанности и от нее не нужно запускаться
  33. // а если не посещали, то значит есть еще 1 компонента связанности поэтому мы увеличиваем ответ на 1
  34. // и снова запускаемся и т.д
  35. if (!used[i])
  36. {
  37. DFS(i, e, used);
  38. count++;
  39. }
  40. }
  41.  
  42. return count;
  43. }
  44. int main()
  45. {
  46. ifstream fin("input.txt");
  47. ofstream fout("output.txt");
  48.  
  49. int n;
  50. fin >> n;
  51. vector<vector<int>> e(n); // список смежности
  52.  
  53. vector<bool>used(n, false); // массив в котором true если мы эту вершинку посетили, иначе false
  54.  
  55.  
  56. for (int i = 0;i<n;i++) //вводим из матрицы смежности сразу в список смежности для того чтобы было удобнее работать
  57. for (int j = 0; j < n; j++)
  58. {
  59. int x;
  60. fin >> x;
  61. if (x)
  62. e[i].push_back(j);
  63. }
  64.  
  65. fout << CountComponents(e, used, n);
  66.  
  67. fin.close();
  68. fout.close();
  69.  
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement