Graph Route Checker

The problem asks for a way to determine whether there is a route between two nodes in a directed graph. One example is given, where the nodes are connected in a linear fashion. The solution should work for more general cases as well.

Problem

Given an directed graph, design an algorithm to find out whether there is a route between two nodes.
Example:
Input:
A -> B
B -> C
C -> D
Output:
There is a route between nodes A and D.

Solution

This solution is in C++. Our A.I. can create solutions in multiple languages.
by kayakane
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Graph {
public:
	Graph(int n) {
		adj.resize(n);
	}

	void addEdge(int u, int v) {
		adj[u].push_back(v);
	}

	bool isRoute(int u, int v) {
		vector<bool> visited(adj.size(), false);
		queue<int> q;
		q.push(u);
		visited[u] = true;
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			for (int i = 0; i < adj[cur].size(); i++) {
				if (adj[cur][i] == v) {
					return true;
				}
				if (!visited[adj[cur][i]]) {
					q.push(adj[ cur][i]);
					visited[adj[cur][i]] = true;
				}
			}
		}
		return false;
	}

private:
	vector<vector<int>> adj;
};

int main() {
	Graph g(4);
	g.addEdge(0, 1);
	g.addEdge(1, 2);
	g.addEdge(2, 3);
	cout << g.isRoute(0, 3) << endl;
	return 0;
}

A.I. Evaluation of the Solution

The candidate's solution is complete and solves the problem. The candidate has used a breadth-first search approach, which is a good choice for this problem.

Evaluated at: 2022-12-08 10:15:46