323q Could you please help me to solve this problem below ON

323q) Could you please help me to solve this problem below? (ONLY USING C++ PLEASE, SUBJECT IS FROM GRAPHS IN ALGORITHMS CLASS)

SELECT THE CENTRAL METRO STATION(S)

Assume that you are given a map of metro stations connected by single railways in one direction.

A central metro station is the one that is reachable from all other stations via some route.

You are asked to find central metro station(s) for any given metro map.

You have to print out the number of possible central metro station(s), if any, and their names (IDs).

Hint: Assume that info about the metro stations how connected to each other is stored in Adjacency List!

Mission College San Fernand Maclay, Burbank Media Ctr Sonora Panorama City Chatsworth Alameda Burbank Aurpart Oxnard O Glenoaks Van Nuys Brand Broadway Canoga Park Mad North Van Nuys Balboa Villa Monrovia Irwindale Glendora La Verne Pomona Chevy Chase Eagle Ra Figueroa Civic Ct Victory DeSoto Reseda Park Arcadia Duarte Azusa San Dimas Valley Pla Claremont Center verduge Road Glendale Sepulveda North Hollywood Del Ma Universal City Griffith Park. Highland Park Sherman Oaks south Pasadena) Mission Gabriel Heritage Squarel Franklin HiLLs Atwat Southwest Arroyo Dodger Museum Hollywood Highlan Bald Stadi ncoln Heights Rowena Hollywood Vin Hillside Garfield San Gabri Fort El Monte Sunset Village Edendale Holl Sunset Plaza Lincoln Parkd Juncti Melrose Echo Pa LAC-USC Med Ctr Santa Anita Aw Arcught Hill Billy Wild Civic Getty Center Crescent Heights Vermontista Monica Center, Maravilla Pico Aliso LA City College UCLA FomonaiBeverly Temple West Hollywood Century Bewerty Cente Miracle Wilshire/ Wilshire 7thMetro Pershing Mile Weste Civic Ctr Brentwood Whittier Soto Pacific Paljsade Pico Rivera 6th/M Roppongi Wilshire Wilshire Rodeo Robertson Whittier Allen ford Park Wilshire Westlake La Cenega Mue Crenshaw Normandoe McArthur Park Veteran Whittier Atlanti Whitt Central Cienega Pico Veterans Administration La CienegaiCadula Jeffersen Park Dockweiter Dorsey Beach BL Grand Wushire 26th St La Cienega Rancho Park Foshay USC Exposition Pa La Habra Bundy. 20th St 4th St nt village Washingto Culver City Cent Hills, Chesterfield sq Santa M Hyde Park Park Venice Manchester Sepulveda gle wood Fareston Marina Del Rey La Ti Westchester 03rd St Kenneth Hah Terminals 143 Manchest Lynwood Lakewood Norwalk horne Vermont Avala enta Fe prings Hoxi Crenshaw Harbor nd Term Parks MariposalNash Bellflower Ls 5-7 Compton EL SegundeiNash Gahr PAC Fic ocEAN Dougla Rosecrans Artes la Village MarinelRed do Beach Del Amo Cypress La Palma ttan Beach outh Bay Galleria Cypress College Stanton Willow Garden G Pacific Coast Highway Anaheim Orange 5th Street Harbor City Santa Ana st Street Ana Ross College Transit Mall side

Solution

Given:
1. A central metro station is the one reachable from all other stations via the same route.
2. Map of Metro station connected by single railways in ONE direction.

The above points will lead to the below results.
1. From (1), find a node from which we can reach all the nodes in the graph.
2. From (2), the graph is Directed Graph.

We can use Depth First Search (DFS) on all the vertices.
If any DFS, does not visit all the vertices, then that node is not a Central Station.
If DFS visits all the nodes (stations), then it is a Central Station.

CODE:
#include<iostream>
#include<list>

using namespace std;

// variable count to check if all variables are visited.
int count = 0;

class Graph
{
   int V; // No. of vertices
   list<int> *adjList; // Pointer to an array containing adjacency lists
   void DFSUtil(int v, bool visited[]); // A function used by DFS
  
   public:
       Graph(int V); // Constructor
       void addEdge(int v, int w); // function to add an edge to graph
       void DFS(int v); // DFS traversal of the vertices reachable from v
};

// Constructor
Graph::Graph(int V)
{
this->V = V;
adjList = new list<int>[V];
}

// Add edges to Adjacency List.
void Graph::addEdge(int v, int w)
{
adjList[v].push_back(w); // Add w to v’s list.
}

// Recursive DFSUtil to find DFS for particular vertex.
void Graph::DFSUtil(int v, bool visited[])
{
   // This keeps tracks of all the nodes visited.
   count++;
  
// Mark the current node as visited and print it
visited[v] = true;

// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for (i = adjList[v].begin(); i != adjList[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}

// DFS traversal of the vertices reachable from v.
// It uses recursive DFSUtil()
void Graph::DFS(int v)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;

// Call the recursive helper function to print DFS traversal
DFSUtil(v, visited);
}

int main()
{
// Create a graph given in the above diagram
// Number of nodes is 4.
   Graph g(4);
  
   // Adjacency List creation.
   // You can replace this with details from your graph.
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

   // This function will print out all the vertices reachable from every vertex.
   // For any node i, if you find all the other vertices reachable, then it is treated as Central station.
   for(int i=0;i<4;i++){
       count = 0;
       g.DFS(i);
       if (count == 4)
       cout << \"Station \" << i << \" is Central Station\" << endl;
   }

return 0;
}

OUTPUT:
Station 0 is Central Station
Station 1 is Central Station
Station 2 is Central Station