• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Dec 14th, 2019 83 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?