fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <queue>
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7. const int M = 50;
  8. char nodes[M][30];
  9.  
  10. int pos_node = 0;
  11. std::vector<int> adjacent_nodes[M];
  12.  
  13. void init() {
  14.     pos_node = 0;
  15.     for (int i = 0; i < M; ++i) adjacent_nodes[i].clear();
  16. }
  17.  
  18. int get_node() {
  19.     char name[30];
  20.     scanf("%s", name);
  21.     for (int i = 0; i < pos_node; ++i)
  22.         if (!strcmp(name, nodes[i]))
  23.             return i;
  24.     strcpy(nodes[pos_node++], name);
  25.     return pos_node-1;
  26. }
  27.  
  28. bool bfs(int source, int sink, std::vector<int> & path) {
  29.     int enqueued[M], prev[M], distance[M];
  30.     memset(enqueued, false, sizeof(enqueued));
  31.     memset(distance, 0, sizeof(distance));
  32.  
  33.     std::queue<int> queue;
  34.     queue.push(source); enqueued[source] = true; prev[source] = source; distance[source] = 0;
  35.     while (not queue.empty()) {
  36.         int cur = queue.front(); queue.pop();
  37.         if (cur == sink) break;
  38.         for (auto next : adjacent_nodes[cur]) {
  39.             if (not enqueued[next]) {
  40.                 queue.push(next); enqueued[next] = true; prev[next] = cur; distance[next] = distance[cur]+1; 
  41.             }     
  42.         }
  43.     }
  44.  
  45.     path.clear();
  46.     if (not enqueued[sink]) return 0;
  47.  
  48.     int now = sink;
  49.     while (prev[now] != now) {
  50.         path.push_back(now);
  51.         now = prev[now];
  52.     }
  53.     path.push_back(source);
  54.     std::reverse(path.begin(), path.end());
  55.     return true;
  56. }
  57.  
  58. void print_path(const std::vector<int> & path) {
  59.     for (int i = 0; i < path.size(); ++i) {
  60.         printf("%s%s", i != 0 ? " -> " : "", nodes[path[i]]);
  61.     }
  62.     printf("\n");
  63. }
  64.  
  65. int main() {
  66.     init();
  67.  
  68.     int n_node;
  69.     scanf("%d", &n_node);
  70.  
  71.     for (int i = 0; i < n_node; ++i) {
  72.         int from = get_node();
  73.         int n_next;
  74.         scanf("%d", &n_next);
  75.         while (n_next--) {
  76.             int to = get_node();
  77.             adjacent_nodes[from].push_back(to);
  78.         }
  79.     }
  80.     int n_query;
  81.     scanf("%d", &n_query);
  82.     while (n_query--) {
  83.         std::vector<int> path;
  84.         int from = get_node(), to = get_node();
  85.         if (bfs(from, to, path)) 
  86.             print_path(path);
  87.         else
  88.             printf("There is no path from %s -> %s\n", nodes[from], nodes[to]);
  89.     }
  90.  
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
8
a 1 b
b 3 c e f
c 2 d g
d 2 c h
e 2 a f
f 1 g
g 1 f
h 2 d g
3
a b
b h
d e
stdout
copy 
a -> b
b -> c -> d -> h
There is no path from d -> e
https://ideone.com/XWH5gY
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!