It has been a prosperous year for King Charles and he is rapidly expanding
his kingdom.A beautiful new kingdom has been recently constructed and in this
kingdom there are many cities connected by a number of one-way roads.
Two cities may be directly connected by more than one roads, this is to
ensure high connectivity.
In this new kingdom King Charles has made one of the cities at his
financial capital and one as warfare capital and he wants high
connectivity between these two capitals.The connectivity of a pair of
cities say city A and city B is defined as the number of different
paths from city A to city B. A path may use a road more than once
if possible. Two paths are considered different if they do not
use exactly the same sequence of roads.
There are N cities numbered 1 to N in the new kingdom and M one-way roads
. City 1 is the monetary capital and city N is the warfare capital.
You being one of the best programmers in new kingdom need to answer the
connectivity of financial capital and warfare capital ,
i.e number of different paths from city 1 to city N.
Input Description:
First line contains two integers N and M.
Then follow M lines ,each having two integers say x and y, 1<=x,y<=N ,
indicating there is a road from city x to city y.
Output Description:
Print the number of different paths from
city 1 to city N modulo 1,000,000,000(10^9).
If there are infinitely many different paths
print "INFINITE PATHS"(quotes are for clarity).
Sample Input:
5 5
1 2
2 4
2 3
3 4
4 5
Sample Output:
2
Sample Input:
5 5
1 2
4 2
2 3
3 4
4 5
Sample Output:
INFINITE PATHS
Constraints:
2<=N<=10,000(10^4)
1<=M<=1,00,000(10^5)
Two cities may be connected by more than two roads and in that case
those roads are to be considered different for counting distinct paths
/*
* KingdomConnectivity.c
* InterviewStreet
*
* Created by Kyle Donnelly on 12/16/12.
*
* Recursively finds the number of paths across a directed graph.
*
* Inputs:
* Number of cities and roads.
* Two integers: city where the road starts and city where it
ends (index 1).
* Two integers: City id (number) which is the monetary capital
* City id (number) which is the war
capital.
* By default these would be 1 and N
for interviewstreet.
*
* Outputs:
* Number of paths from city 1 to city N (modulo MOD_LIMIT).
*
* Base case:
* Current city is the destination, return 1.
*
* Recursive case:
* Current city is not destination
* add up the number of paths of each city this one has access to.
*
* This program forces you to stop once you reach the destination.
*
*/
#include
#include
#include
#define MOD_LIMIT 1000000000
typedef struct {
unsigned int id;
struct _list *children;
unsigned int distance;
} graph;
typedef struct _list {
struct _list *next;
graph *g;
} list;
typedef enum {
UNVISITED, VISITED, LOOPED
} status;
static status *visited; // array of city statuses
static graph **cities; // array of city pointers
static jmp_buf buf; // for loops
/* push a graph into a list of graphs */
void push_graph (list **head, graph *g) {
list *cur;
if (*head == NULL) {
cur = *head = malloc(sizeof(list));
}
else {
for (cur = *head; cur->next != NULL; cur = cur->next);
cur = cur->next = malloc(sizeof(list));
}
cur->g = g;
cur->next = NULL;
}
unsigned int find_paths (graph *source, graph *destination) {
unsigned int retval = 0;
list *cur;
if (source == destination) {
/* Awesome, we made it */
return 1;
}
if (visited[source->id - 1] == VISITED) {
/*
* Loop in graph!
* Not sure if this city actually leads to destination though.
* If not then we don't care.
* Alert earlier paths.
*/
visited[source->id - 1] = LOOPED;
return 0;
}
if (source->distance != -1) {
/* Already know how many from here */
return source->distance;
}
/* Mark that we've gone through this city already */
visited[source->id - 1] = VISITED;
for (cur = source->children; cur != NULL; cur = cur->next) {
/* Check how many paths there are for each child city */
retval = (retval + find_paths(cur->g, destination)) % (MOD_LIMIT);
}
/* Store for future paths through this city */
source->distance = retval;
/* Mark that we're done with this city */
if (visited[source->id - 1] == LOOPED) {
/* One of the paths led back here! */
if (retval > 0) {
/* There is a loop on the way to the destination! */
longjmp(buf, 1);
}
/* But this city didn't lead to the destination anyway */
}
visited[source->id - 1] = UNVISITED;
return (retval);
}
int main() {
unsigned int n, m, to, from, money, war;
unsigned int num_paths;
scanf("%u %u", &n, &m);
cities = malloc(sizeof(graph *) * n);
visited = malloc(sizeof(status) * n);
for (unsigned int i=0; i cities[i] = malloc(sizeof(graph));
cities[i]->id = i+1;
cities[i]->children = NULL;
cities[i]->distance = -1;
visited[i] = UNVISITED;
}
for (unsigned int i=0; i scanf("%u %u", &from, &to);
/* Add node to parent's children */
push_graph(&(cities[from-1]->children), cities[to-1]);
}
scanf("%u %u", &money, &war);
if (!(setjmp(buf))) {
/* Try this */
num_paths = find_paths(cities[money-1], cities[war-1]);
printf("%u\n", num_paths);
}
else {
/* If there are infinite paths just print that */
printf("INFINITE PATHS\n");
}
return 0;
}
