Problem

Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
Example:
Input:
Node 1: A
Node 2: B
Output:
true

Solution

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Node {
public:
    Node(int val) : val(val) {}
    int val;
    vector<Node*> neighbors;
};

bool isRoute(Node* start, Node* end) {
    if (start == end) return true;
    queue<Node*> q;
    q.push(start);
    while (!q.empty()) {
        Node* curr = q.front();
        q.pop();
        for (Node* neighbor : curr->neighbors) {
            if (neighbor == end) return true;
            q.push(neighbor);
        }
    }
    return false;
}

int main() {
    Node* a = new Node(1);
    Node* b = new Node(2);
    Node* c = new Node(3);
    Node* d = new Node(4);
    Node* e = new Node(5);
    Node* f = new Node( 6);
    a->neighbors.push_back(b);
    a->neighbors.push_back(c);
    b->neighbors.push_back(d);
    c->neighbors.push_back(e);
    d->neighbors.push_back(f);
    cout << isRoute(a, f) << endl;
    cout << isRoute(a, e) << endl;
    cout << isRoute(a, a) << endl;
    cout << isRoute(a, b) << endl;
    cout << isRoute(a, c) << endl;
    cout << isRoute(a, d) << endl;
    cout << isRoute(a, e) << endl;
    cout << isRoute(a, f) << endl;
    return 0;
}