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;
  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
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. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top