CC150 4.2

4_2.cpp

/* CC150 4.2
 * Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
 */

#include <iostream>
#include <list>

using namespace std;

class Graph {
public:
	Graph(int n) : V(n), adj(new list<int>[V]) {}
	~Graph() { delete[] adj; }
	void addEdge(int v, int w) { adj[v].push_back(w); } // add w to v's adjacent list
	bool isConnected(int v1, int v2);
private:
	int V; // number of vertices
	list<int> *adj; // array of adjacent lists
	void DFSUtil(int v, int w, bool visited[]); // DFS starting from v to w
};

void Graph::DFSUtil(int v, int w, bool visited[])
{
	visited[v] = true;
	if (visited[w])
		return;
	for (auto it = adj[v].begin(); it != adj[v].end(); ++it) {
		if (!visited[*it])
			DFSUtil(*it, w, visited);
		if (visited[w])
			return;
	}
}

bool Graph::isConnected(int v1, int v2)
{
	bool *visited = new bool[V];
	for (int i = 0; i != V; ++i)
		visited[i] = false;
	DFSUtil(v1, v2, visited);
	if (visited[v2])
		return true;
	else
		return false;
}

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