fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int numNode, numEdge;
  5. map<char, int> node;
  6. vector<char> id;
  7. vector<vector<int>> adj;
  8. void bfs(char start, char finish) {
  9.     queue<int> q;
  10.     vector<int> pre(numNode, -2);
  11.     pre[node[start]] = -1;
  12.     q.push(node[start]);
  13.     bool hasPath = false;
  14.     while(!q.empty()) {
  15.         int u = q.front();
  16.         q.pop();
  17.         if(u == node[finish]) {
  18.             hasPath = true;
  19.             break;
  20.         }
  21.         for(int v : adj[u]) if(pre[v] == -2) {
  22.             pre[v] = u;
  23.             q.push(v);
  24.         }
  25.     }
  26.     if(hasPath == false) {
  27.         cout << "no_path\n";
  28.         return;
  29.     }
  30.     vector<char> path;
  31.     int u = node[finish];
  32.     while(u != -1) {
  33.         path.push_back(id[u]);
  34.         u = pre[u];
  35.     }
  36.     reverse(path.begin(), path.end());
  37.     for(char x : path) cout << x << " ";
  38.     cout << '\n';
  39. }
  40. int main() {
  41.     cin >> numNode >> numEdge;
  42.     id.resize(numNode);
  43.     adj.resize(numNode);
  44.     for(int i = 0; i < numNode; i++) {
  45.         char x;
  46.         cin >> x;
  47.         node[x] = i;
  48.         id[i] = x;
  49.     }
  50.     for(int i = 0; i < numEdge; i++) {
  51.         char x, y;
  52.         cin >> x >> y;
  53.         adj[node[x]].push_back(node[y]);
  54.     }
  55.     int numQuery;
  56.     cin >> numQuery;
  57.     for(int i = 0; i < numQuery; i++) {
  58.         char start, finish;
  59.         cin >> start >> finish;
  60.         bfs(start, finish);
  61.     }
  62.     return 0;
  63. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
6 13
W K I U M Q
W M
W Q
I W
I K
I U
I M
U W
U K
U Q
M U
M Q
Q I
Q M
3
U I   
W K
K M
stdout
copy 
U Q I 
W M U K 
no_path
https://ideone.com/qtfAdA
language:
C++ (gcc 8.3)
created:
3 days 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!