Guest User

Untitled

a guest
Dec 14th, 2019
89
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <iostream>
  3. #include <queue>
  4. #include <math.h>
  5.  
  6. class MatrixGraph {
  7.  
  8. public:
  9.  
  10. std::vector<std::vector<size_t>> data;
  11.  
  12. MatrixGraph(size_t N);
  13.  
  14. ~MatrixGraph() {};
  15.  
  16. void AddEdge(size_t from, size_t to);
  17.  
  18. };
  19.  
  20.  
  21. MatrixGraph::MatrixGraph(size_t N) {
  22. for (size_t i = 0; i < N; i++) {
  23. std::vector<size_t> tmp;
  24. data.push_back(tmp);
  25. }
  26.  
  27. }
  28.  
  29.  
  30. void MatrixGraph::AddEdge(size_t from, size_t to) {
  31. data.at(from).push_back(to);
  32. data.at(to).push_back(from);
  33. }
  34.  
  35.  
  36. int main()
  37. {
  38. size_t N, M;
  39. std::cin >> N >> M;
  40. MatrixGraph graph(N);
  41.  
  42. for (size_t i = 0; i < M; i++) {
  43. size_t from, to;
  44. std::cin >> from >> to;
  45. graph.AddEdge(from, to);
  46. }
  47. size_t a, b;
  48. std::cin >> a >> b;
  49. std::queue<int> q;
  50. q.push(a);
  51. std::vector<bool> used(N);
  52. std::vector<int> d(N), res1(N), p(N);
  53. d[a] = 0;
  54. used[a] = true;
  55. p[a] = -1;
  56. res1[a] = 1;
  57. while (!q.empty()) {
  58. int v = q.front();
  59. q.pop();
  60. std::vector<size_t> Vertices = graph.data[v];
  61. for (size_t i = 0; i < Vertices.size(); i++) {
  62. int to = Vertices[i];
  63. if (!used[to]) {
  64. used[to] = true;
  65. q.push(to);
  66. d[to] = d[v] + 1;
  67. p[to] = v;
  68. res1[to] = res1[v];
  69. }
  70. else if (d[v] == d[to] - 1 && p[to] != v) res1[to] += res1[v];
  71. }
  72. }
  73.  
  74. std::cout << res1[b];
  75. return 0;
  76. }
RAW Paste Data