50189. Find a Path

I'm a slow walker, but I never walk backwards.

Task Description

You are going to write a program to check whether two cities are connected by a path. There are unknown number of cities and $M$ roads. Every road connects two cities. Two cities $a$ and $b$ are connected by a path, i.e., a sequence of cities, where the first city in the path is $a$, the last city is $b$, and every two adjacent cities in the sequence are connected by a road.

Please refer to the following figure. Each road is represented by a pair of city indices. You need to build an object to store these roads. Note that the indices of cities is from $0$ to a very large $N$, therefore you cannot use two dimensional array to store the roads as before, or your program will get a RE or an MLE. Then, you will be given a sequence of pairs of city indices, and determine if the two cities are connected by a path or not.

RoadsRoads

We suggest the following approach to solve this problem. First, design a structure Graph, and put all roads into Graph. Then, sort these roads by their starting city indices. As a result, all roads from the same city will be placed together for easy access. You need to use qsort to quickly sort these roads. Using a bubble sort will cause TLE. Please refer to Figure 1.

Then, build a mapping array from the city index to the first road leaving this city. That is, when given a city index, we can easily find the destination of all roads leaving the city from Graph. One easily build this mapping in which the indices in the mapping are sorted from the sorted edge sets. Please refer to Figure 2.

figure 1. sorted Graphfigure 1. sorted Graph
figure 2. Mapfigure 2. Map

Finally, you need to determine if a given pair of city indices, $a$ and $b$, are connected by a path or not. For this we suggest the following approach. First we use a binary search to search the map for $a$, and get the pointer into Graph for all cities that $a$ can reach. For example, city $3$ can reach cities 2, 10, and 50. Then we recursively go from these cities and see if we reach $b$. Note that you need to remember the set of cities you have already visited so you do not visit the same city twice.

We suggest the following structure and functions.

#include <stdbool.h>
typedef struct _graph {
    // design your object here
} Graph;
typedef struct _map{
    // design your object here
} Map
 
void init(Graph *graph, int M); // initialize graph
void addRoad(Graph *graph, int city1, int city2); // add roads into graph
void normalized(Graph *graph, Map *map)  // sort the roads by indices and build the map.
bool hasPath(Graph *graph, Map *map, int city1, int city2);// check if two cities are connected

Input Format

The first line contains one integer $M$, the number of roads in the graph. Each of the following $M$ lines contains two city indices of a road. The next line contains one integer $Q$, the number of queries. Each of the following $Q$ lines contains two city indices to check if there is a path between them.

  • $M \leq 10000$
  • $Q \leq 200$

Output Format

For each query, print “There is a path.” when there is a path between the given two cities, otherwise print “There is no path.”.

Sample input 1

6
100 2
3 50
50 2
3 10
20 200
3 2
8
200 20
20 200
100 10
50 100
100 200
30 2
3 40
30 40

Sample output 1

There is a path.
There is a path.
There is a path.
There is a path.
There is no path.
There is no path.
There is no path.
There is no path.

Sample Input 2

Sample Inupt 2

Sample Output 2

Sample Output 2

Sample Input 3

Sample Inupt 3

Sample Output 3

Sample Output 3

Discussion