SARAWAK HYDROGEN FUEL CELL BUS
The Sarawak Bus Company (SBCom) has invested in a more modern form of transport, Hydrogen
Fuel Cell Buses. SBCom has built a bus route network with n stations. However, SBCom has retained
his commitment to free the passenger from the burden of too many choices: from each station, a
passenger can catch a bus to exactly one other station. Such a journey is referred to as a leg. Note
that this is a one-way journey, and it might not be possible to get back again.
SBCom also offers exactly one choice of ticket, which allows a passenger to travel up to k legs in one
trip. At the exit from each station is an automated ticket reader (only one, so that passengers do not
need to decide which to use). The reader checks that the distance from the initial station to the final
station does not exceed k legs. Each ticket reader must be programmed with a list of valid starting
stations, but the more memory this list needs, the more expensive the machine will be. Help SBCom
by determining, for each station A, the number of stations (including A) from which a customer can
reach A in at most k legs.