VIACST - Editorial


Mumbai N00B


Author: Vatsal Kanakiya
Tester: Dipen Ved
Editorialist: Vinitra M K






Graph Theory


In the first line you are given N (no of stations in a railway system) and M (no of tracks in the system).
In the following M lines you are pair of numbers(A and B), denoting stations with a track connecting them.
You are also given 4 space-separated numbers (X,Z,Y,K).
You need to find number of ways to travel from X to Y through Z, and every route should contain exactly K
tracks in all.


You can find the no of routes from X to Y, through Z, first by counting no of routes from of X to Z with
depth i where 1<=i<=k-1 Then you count the number of routes from Z to Y, with depth (k-i) where 1<=i<=k-1
and multiply both these numbers, to get total routes no of routes from X to Y through Z.


The problem can be solved by DFS theory of graph. DFS stands for Depth First Search.
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts
at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible
along each branch before backtracking.

We will start by taking values of m pairs and maintaining an adjacency list of the connected nodes. An adjacency
list is a list which keeps a track every node in the graph and to which other nodes it is connected. Then two
DFS function calls will be placed. First DFS call will be placed to find out no of routes, from X to Z, which
will be stored in an array. The second DFS call will be placed to find out the no of routes from Z to Y which
will be stored in another array.

The DFS function for this problem, will therefore have 6 parameters:

dfs(int source, int dest, ll ab[], vector <int> adj[], int depth, int k)

source is the starting node and dest is the terminating node.
array ab[] will be used to store no of routes from start to dest of particular depth. For second dfs call, the
array used will be bc[] vector adj[] is the adjacency list which has records of connected nodes.
The integer variable depth will be initialized to zero when calling from the main function.
The integer variable k denotes maximum no of tracks that a route can have.

Thus the code for that looks like this:

dfs(a, b, ab, adj, 0, k);
dfs(b, c, bc, adj, 0, k);

We will keep calling the dfs function till source becomes equal to destination.

First we will find out the no of nodes the current node is connected to and then traverse to those connected
nodes till source==destination. The code for it will look like this:

int sz=adj[source].size();
for(int i=0; i< sz; i++) {
	dfs(adj[source][i], dest, ab, adj, depth+1, k);

Since the source!=destination, we will increment the depth by 1, i.e we are keeping record of no of tracks in that route.

Once source==destination we will increment ab[depth] by 1, which means no of paths from source to destination
having a particular depth.

The same will be done for other DFS call as well.

Finally the no of paths having k tracks, between X and Y is calculated.
We first take a variable c, initialized to zero.
Then evaluate no of paths from X to Z, with depth i where 1<=i<=k-1.
Then evaluate no of paths from Z to Y, with depth k-i where 1<=i<=k-1.
Multiply both and add it to c.


Solution can be found here.