Lösungsskizze Railroad
======================

Da es Maus Stofl nur darauf ankommt, wie oft er umsteigen muss, sind die Fahrtzeiten völlig egal. Das Eisenbahnnetz ist also ein ungewichteter, ungerichteter Graph in welchem wir alle Kanten finden wollen, die für einen kürzesten Weg von S nach E unverzichtbar sind. Um diese Kanten zu finden, führen wir zwei Breitensuchen durch, eine von S aus und eine von E aus. Dies gibt uns die Distanz D, die Distanz von S zu E. Für ein Knoten v sei DS(v) die Distanz von S zu v (berechnet für alle v mit der BFS von S aus) und DE(v) die Distanz von v zu E. Eine Kante (v,w) kann nun genau dann auf dem kürzesten Weg von S nach E liegen, wenn DS(v)+1+DE(w) = D oder DS(w)+1+DE(v) = D gilt. Um nun nur die unentbehrlichen Kanten von S nach E zu finden, merken wir uns pro Distanz zu S, wie viele solche Kanten wir finden. Für jede Distanz <= D, für die es nur eine solche Kante gibt, ist jene Kante unentbehrlich. Gibt es für eine Distanz zu S mehrere Kanten, die auf einem kürzesten Weg von S nach E liegen können, so ist keine dieser Kanten unentbehrlich. Denn wenn wir eine dieser Kanten entfernen, so gibt es immer noch einen kürzesten Weg von S nach E der Länge D, nämlich jener der bei dieser Distanz eine der anderen Kanten benützt.

Speicher: O(N+M)
Laufzeit: O(N+M)