﻿

# 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;
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