import java.util.*;

import java.io.*;

class Vertex {

// Constructor: set name, chargingStation and index according to given values,

// initilaize incidentRoads as empty array

public Vertex(String placeName, boolean chargingStationAvailable, int idx) {

name = placeName;

incidentRoads = new ArrayList();

index = idx;

chargingStation = chargingStationAvailable;

}

public Vertex(String placeName, boolean hasChargingStataion) {

}

public String getName() {

return name;

}

public boolean hasChargingStation() {

return chargingStation;

}

public ArrayList getIncidentRoads() {

return incidentRoads;

}

// Add a road to the array incidentRoads

public void addIncidentRoad(Edge road) {

incidentRoads.add(road);

}

public int getIndex() {

return index;

}

private String name; // Name of the place

ArrayList incidentRoads; // Incident edges

private boolean chargingStation; // Availability of charging station

private int index; // Index of this vertex in the vertex array of the map

public void setVisited(boolean b) {

}

public Edge[] getAdjacentEdges() {

return null;

}

public boolean isVisited() {

return false;

}

public boolean isChargingStationAvailable() {

return false;

}

}

class Edge {

public Edge(int roadLength, Vertex firstPlace, Vertex secondPlace) {

length = roadLength;

incidentPlaces = new Vertex[] { firstPlace, secondPlace };

}

public Edge(Vertex vtx1, Vertex vtx2, int length2) {

}

public Vertex getFirstVertex() {

return incidentPlaces[0];

}

public Vertex getSecondVertex() {

return incidentPlaces[1];

}

public int getLength() {

return length;

}

private int length;

private Vertex[] incidentPlaces;

public Vertex getEnd() {

return null;

}

}

//A class that represents a sparse matrix

public class RoadMap {

// Default constructor

public RoadMap() {

places = new ArrayList();

roads = new ArrayList();

}

// Auxiliary function that prints out the command syntax

public static void printCommandError() {

System.err.println("ERROR: use one of the following commands");

System.err.println(" - Load a map and print information:");

System.err.println(" java RoadMap -i ");

System.err.println(" - Load a map and determine if two places are connnected by a path with charging stations:");

System.err.println(" java RoadMap -c ");

System.err.println(" - Load a map and determine the mininmum number of assistance cars required:");

System.err.println(" java RoadMap -a ");

}

public static void main(String[] args) throws Exception {

if (args.length == 2 && args[0].equals("-i")) {

RoadMap map = new RoadMap();

try {

map.loadMap(args[1]);

} catch (Exception e) {

System.err.println("Error in reading map file");

System.exit(-1);

}

System.out.println();

System.out.println("Read road map from " + args[1] + ":");

map.printMap();

System.out.println();

}

else if (args.length == 2 && args[0].equals("-a")) {

RoadMap map = new RoadMap();

try {

map.loadMap(args[1]);

} catch (Exception e) {

System.err.println("Error in reading map file");

System.exit(-1);

}

System.out.println();

System.out.println("Read road map from " + args[1] + ":");

map.printMap();

int n = map.minNumAssistanceCars();

System.out.println();

System.out.println("The map requires at least " + n + " assistance car(s)");

System.out.println();

}

else if (args.length == 4 && args[0].equals("-c")) {

RoadMap map = new RoadMap();

try {

map.loadMap(args[1]);

} catch (Exception e) {

System.err.println("Error in reading map file");

System.exit(-1);

}

System.out.println();

System.out.println("Read road map from " + args[1] + ":");

map.printMap();

int startVertexIdx = -1, endVertexIdx = -1;

try {

startVertexIdx = Integer.parseInt(args[2]);

endVertexIdx = Integer.parseInt(args[3]);

} catch (NumberFormatException e) {

System.err.println("Error: start vertex and end vertex must be specified using their indices");

System.exit(-1);

}

if (startVertexIdx < 0 || startVertexIdx >= map.numPlaces()) {

System.err.println("Error: invalid index for start vertex");

System.exit(-1);

}

if (endVertexIdx < 0 || endVertexIdx >= map.numPlaces()) {

System.err.println("Error: invalid index for end vertex");

System.exit(-1);

}

Vertex startVertex = map.getPlace(startVertexIdx);

Vertex endVertex = map.getPlace(endVertexIdx);

if (!map.isConnectedWithChargingStations(startVertex, endVertex)) {

System.out.println();

System.out.println("There is no path connecting " + map.getPlace(startVertexIdx).getName() + " and "

+ map.getPlace(endVertexIdx).getName() + " with charging stations");

} else {

System.out.println();

System.out.println("There is at least one path connecting " + map.getPlace(startVertexIdx).getName() + " and "

+ map.getPlace(endVertexIdx).getName() + " with charging stations");

}

System.out.println();

} else {

printCommandError();

System.exit(-1);

}

}

public void loadMap(String filename) {

File file = new File(filename);

places.clear();

roads.clear();

try {

Scanner sc = new Scanner(file);

//Read the first line: number of vertices and number of edges

int numVertices = sc.nextInt();

int numEdges = sc.nextInt();

for (int i = 0; i < numVertices; ++i) {

// Read the vertex name and its charing station flag

String placeName = sc.next();

int charginStationFlag = sc.nextInt();

boolean hasChargingStataion = (charginStationFlag == 1);

// Create a new vertex using the information above and add it to places

Vertex newVertex = new Vertex(placeName, hasChargingStataion, i);

places.add(newVertex);

}

for (int j = 0; j < numEdges; ++j) {

// Read the edge length and the indices for its two vertices

int vtxIndex1 = sc.nextInt();

int vtxIndex2 = sc.nextInt();

int length = sc.nextInt();

Vertex vtx1 = places.get(vtxIndex1);

Vertex vtx2 = places.get(vtxIndex2);

Edge newEdge = new Edge(length, vtx1, vtx2);

Edge reverseEdge = new Edge(length, vtx2, vtx1);

vtx1.addIncidentRoad(newEdge);

vtx2.addIncidentRoad(reverseEdge);

roads.add(newEdge);

}

sc.close();

} catch (Exception e) {

e.printStackTrace();

places.clear();

roads.clear();

}

}

the question is :

//Check if two vertices are connected by a path with charging stations on each itermediate vertex.

//Return true if such a path exists; return false otherwise.

//The worst-case time complexity of your algorithm should be no worse than O(v + e),

//where v and e are the number of vertices and the number of edges in the graph.

starting with

public boolean isConnectedWithChargingStations(Vertex startVertex, Vertex endVertex) {

if (startVertex.getIndex() == endVertex.getIndex()) {

return true;

}