SHARE
TWEET

Untitled

a guest Dec 13th, 2018 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*Дан невзвешенный неориентированный граф.
  2. В графе может быть несколько кратчайших путей
  3. между какими-то вершинами. Найдите количество
  4. различных кратчайших путей между заданными
  5. вершинами. Требуемая сложность O(V+E).*/
  6.  
  7. #include <vector>
  8. #include <queue>
  9. #include <list>
  10. #include <iostream>
  11.  
  12. using std::vector;
  13. using std::queue;
  14. using std::cin;
  15. using std::cout;
  16.  
  17. int countPaths(vector<vector<int>> graph, int n, int from, int to)
  18. {
  19.     vector<int> used(n), depth(n), parent(n), path_counter(n,0);
  20.     int s = from;
  21.     queue<int> q;
  22.     q.push(s);
  23.     used[s] = 1;
  24.     depth[s] = 0;
  25.     parent[s] = -1;
  26.     while (!q.empty()){
  27.         int current_vertex = q.front();
  28.         q.pop();
  29.         for(int i = 0; i < n; i++){
  30.             int next_vertex = i;
  31.             int road = graph[current_vertex][next_vertex];
  32.             if(!road) continue;
  33.             if(!used[next_vertex]){
  34.                 q.push(next_vertex);
  35.                 used[next_vertex] = 1;
  36.                 depth[next_vertex] = depth[current_vertex] + 1;
  37.                 parent[next_vertex] = current_vertex;
  38.                 path_counter[next_vertex]++;
  39.             } else if (depth[next_vertex] == depth[current_vertex] + 1) path_counter[next_vertex]++;
  40.         }
  41.     }
  42.     return path_counter[to];
  43. }
  44.  
  45. int main()
  46. {
  47.     unsigned int n = 0;
  48.     cin >> n;
  49.     vector<vector<int>> graph(n, vector<int>(n,0));
  50.     int k;
  51.     cin >> k;
  52.     for(int i = 0; i < k; i++){
  53.         int a, b;
  54.         cin >> a >> b;
  55.         graph[a][b] = 1;
  56.         graph[b][a] = 1;
  57.     }
  58.  
  59.     int from = 0;
  60.     int to = 0;
  61.     cin >> from >> to;
  62.  
  63.     cout << countPaths(graph, n, from, to);
  64. }
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
 
Top