Runde 2H

Übersicht

AufgabeSubtask 1
dfs (0/20)0/20
bfs (0/20)0/20
dijkstra (0/20)0/20
bsearch (0/20)0/20
prefixsum (0/20)0/20

Hier siehst du, welche Aufgaben du bereits gelöst hast. Lass dich nicht aufhalten und such dir oben eine Aufgabe aus, die du lösen willst!

Details und Informationen zur Runde 2H findest du hier.

Tiefensuche

Diese und die nächsten paar Aufgaben handeln von der sogenannten Graphentheorie. Wenn du das Wort “Graphentheorie” nun gerade zum ersten Mal hörst/liest, sagt dir das vermutlich nicht viel. “Graphein” ist griechisch für “schreiben”, was auch nicht viel aussagt. Mit dem Zeichnen zweidimensionaler Funktionsgraphen, das du vielleicht aus dem Mathematikunterricht kennst, hat es auch nichts zu tun. Und “Theorie” soll hier nicht heissen, dass es sich um ungetestete Behauptungen handelt, sondern vielmehr um allgemeine Konzepte, die in sehr vielen Situationen anwendbar sind.

Problembeschreibung

Was ist ein Graph?

Als Graphen bezeichnen wir eine Menge von Punkten und Verbindungen zwischen diesen Punkten. Die Punkte werden meist Knoten und die Verbindungen zwischen Punktepaaren meist Kanten genannt. Im Bild 1 siehst du ein Beispiel eines solchen Graphen. Jeder Kreis ist ein Knoten und jede Linie, die zwei solche Knoten verbindet, ist also eine Kante.

2H DFS graph example

Bild 1: Ein Beispiel für einen Graphen mit 6 Knoten und 5 Kanten.

Dieser Graph besteht also aus 6 Knoten und 5 Kanten. Eine der fünf Kanten verläuft zwischen Knoten 2 und 3, daher sagen wir, dass Knoten 2 mit Knoten 3 benachbart ist. Die beiden Knoten sind auch indirekt benachbart, nämlich über den gemeinsamen Nachbarn 4. Häufig sprechen wir von der Nachbarschaft eines Knotens, was einfach die Menge aller Nachbarn bezeichnet. Die Nachbarschaft von 3 sind die Knoten 1, 2 und 4 und die Nachbarschaft von 2 sind die Knoten 3 und 4.

Einen Graphen so aufzuzeichnen ist eine Art ihn darzustellen. Auf die genaue Zeichnungsart kommt es uns aber gar nicht an. Wenn wir die Knoten ein wenig verschieben und die Kanten entsprechend mitbewegen, sagen wir immer noch, dass dies derselbe Graph ist. Es muss auch gar nicht unbedingt eine solche Zeichnung sein, wir können einen Graphen auch einfach als abstrakte Liste von Knoten und Kanten beschreiben. Dazu benennen wir oft die Knotenmenge mit V (Englisch vertices) und die Kantenmenge mit E (Englisch edges). Das Beispiel im Bild 1 wäre dann V = {1, 2, 3, 4, 5, 6} und E = {{1, 3}, {2, 3}, {2, 4}, {3, 4}, {5, 6}}. Die Anzahl Knoten bezeichnen wir meist mit n (im Beispiel ist n = 6) und die Anzahl Kanten mit m (im Beispiel ist m = 5).

Wie sieht ein Graph im Computer aus?

Wenn wir nun in einer Aufgabe der SOI einem solchen Graphen begegnen, so ist dieser meist nicht als Bild gegeben, sondern als solch eine abstrakte Auflistung der Knoten und Kanten. Die Knoten sind dann meist einfach von 1 bis n nummeriert und so enthält die Eingabe nur eine Zeile mit n und m und dann m Zeilen mit den Punktepaaren der m Kanten. Etwa so (für das Beispiel in Bild 1):

6 5
1 3
2 3
2 4
3 4
5 6

Und was machen wir jetzt damit? Wie repräsentieren wir diesen Graphen nun in unserem Programm, sodass wir nützliche Dinge damit anstellen können? Wir könnten einfach diese Kantenliste so einlesen und abspeichern. In C++ sähe das vielleicht etwa so aus:

int n = 6;
int m = 5;
vector<pair<int,int>> E = {{1,3}, {2,3}, {2,4}, {3,4}, {5,6}};

Eine solche Kantenliste ist manchmal gut genug und kann alles was wir brauchen. Häufig aber wollen wir auf den Nachbarschaften von Knoten operieren, d.h. wir wollen alle Nachbarn eines Knotens x abfragen, was mit einer Kantenliste nur möglich ist, indem wir alle Kanten durchgehen und schauen ob x irgendwo vorkommt.

SOI-typische Graphenaufgaben haben oft bis zu 100 000 Kanten, und da kann eine solche lineare Suche durch die Kantenliste schon mal etwas länger dauern. Deshalb ist die nützlichste Speicherart für Graphen eine andere, nämlich die sogenannte Adjazenzliste. Die Idee ist simpel: Statt einer grossen langen Liste mit allen Kanten merken wir uns für jeden Knoten eine separate Liste mit all seinen Nachbarn. Die Datenstruktur besteht also aus n Listen, und wenn wir die Nachbarschaft des Knotens x wissen wollen, schauen wir einfach die x-te dieser Listen an.

Implementieren lässt sich das in C++ ganz leicht mittels Vektoren, den Arrays dynamischer Grösse (hat nicht viel mit den Vektoren aus der Mathe zu tun). Wir verschachteln dazu n Vektoren in einen grossen Vektor - die inneren Vektoren sind die Nachbarschaftslisten und der äussere Vektor hält sie alle zusammen. Ein wenig müssen wir noch wegen der nullbasierten Indexierung aufpassen: entweder wir wandeln alles in nullbasierte Indexierung um (was häufig einfacher geht), oder wir fügen einfach noch einen imaginären Knoten 0 ohne Nachbarn hinzu:

int n = 6;
int m = 5;
// Erste Variante mit nullbasierte Knoten (von 0 bis n-1 nummeriert):
vector<vector<int>> E = {{2}, {2,3}, {0,2,3}, {1,2}, {5}, {4}};
// oder mit einem 0-ten Knoten ohne Nachbarn:
vector<vector<int>> E = {{}, {3}, {3,4}, {1,3,4}, {2,3}, {6}, {5}};
// Die Nachbarn von Knoten x sind dann in E[x] zu finden.

Was stellt ein Graph dar?

Ein solcher Graph kann nun für alles mögliche stehen - zum Beispiel für den Strassenplan einer Stadt. Die Knoten stehen dann für die Kreuzungen und Plätze der Stadt und die Kanten für die Strassen dazwischen. Was wir häufig wissen wollen ist zum Beispiel der kürzeste Weg zwischen zwei Knoten (Wie komme ich am schnellsten zum Bahnhof?) oder ob es überhaupt möglich ist, von jedem Ort an jeden anderen zu kommen (Gibt es eine Insel von der man nicht mehr wegkommt?).

Manchmal sind dafür noch Zusatzinformationen zu den Knoten und Kanten gegeben, zum Beispiel eine Fahrtzeit pro Kante (ein sogenanntes Kantengewicht) oder eine Richtung pro Kante (z.B. für Einbahnstrassen). In diesem Kapitel schauen wir uns aber vorerst nur mal ungewichtete, ungerichtete Graphen an.

Standardalgorithmus

Was ist nun diese ominöse DFS?

Nun wollen wir uns an den ersten Algorithmus für Graphen heranwagen. Es ist die sogenannte Tiefensuche, oft abgekürzt mit DFS, vom Englischen Depth First Search. Sie ist eine von zwei sogenannten Graphentraversierungsalgorithmen, die in den Rucksack eines jeden Informatik-Olympioniken gehören. Den anderen, die Breitensuche (BFS), schauen wir gleich nachher an. Bei beiden geht es darum, den Graphen systematisch zu erkunden und zu entdecken oder eben zu traversieren.

Stell dir vor du steckst mitten in einem Labyrinth. Das Labyrinth beschreiben wir als Graphen mit den Räumen als Knoten und den Gängen zwischen den Räumen als Kanten. Wir stecken nun völlig verloren im Raum/Knoten Nr. 1 und suchen den Ausgang (sei dies Knoten n). Alle Räume sehen etwa gleich aus und wir haben keinen Lageplan, kein GPS, kein Wifi und auch sonst kaum Hilfsmittel. Alles was wir haben ist ein langer roter Faden und ein grosser Topf mit roter Farbe.

Wie finden wir nun den Ausgang aus dem Labyrinth? Unsere Strategie ist die folgende: Wir fixieren den Faden, den wir nachher während unserem Erkundungsgang abrollen werden, in unserem Startraum, sodass wir den Weg zurück zu diesem Startraum stets wieder finden können. Ausserdem malen wir einen roten Punkt auf den Boden, um zu markieren, dass wir den Startraum schon besucht haben. Wir starten in eine beliebige Richtung und machen in jedem neuen Raum folgendes: Wir malen einen roten Punkt auf den Boden, damit wir wissen, dass wir hier schon waren und klappern dann der Reihe nach von links nach rechts alle ausgehenden Gänge ab. Das heisst wir gehen zuerst dem linkesten Gang entlang und kommen so wieder in einen neuen Raum. Dort bringen wir eine Markierung an und gehen wieder dem linkesten Gang nach weiter. Irgendwann kommen wir so in eine Sackgasse oder in einen Raum in dem wir schon einmal waren (der also schon eine rote Markierung auf dem Boden hat). In einem solchen Fall kehren wir einfach um und gehen zurück zum Raum aus dem wir gekommen sind (der rote Faden sagt uns wo das war). Von dort probieren wir es mit dem nächsten Gang, den es noch zu erkunden gilt (den nächsten von links) und wiederholen das gleiche Verfahren. So probieren wir systematisch Gang für Gang durch. Haben wir auch den letzten, rechtesten Gang erkundet, so beenden wir die Suche in diesem Raum und gehen einen Gang zurück in Richtung Startraum (indem wir dem roten Faden folgen). Auf diese Weise finden wir früher oder später den Ausgang oder wissen, dass er vom Start aus unerreichbar ist.

Algorithmus: Tiefensuche

Genau so funktioniert nun auch die Tiefensuche. Den Farbtopf simulieren wir mit einem booleschen Array, also einem Bit pro Raum, mit dem wir uns merken, ob wir einen bestimmten Raum schon besucht haben oder nicht. Den Faden repräsentieren wir nur implizit, nämlich mit dem rekursiven Aufruf-Stack unserer DFS-Funktion. Das heisst in jedem Aufruf der DFS-Funktion besuchen wir einen neuen Knoten und rufen die Funktion rekursiv für alle von dort benachbarten, noch nicht besuchten Knoten auf. In C++ Code sieht das dann etwa so aus:

// Wir nehmen an, dass E eine nullbasierte Adjazenzliste darstellt.
vector<vector<int>> E;
vector<int> visited;

void dfs(int v) {
        // Wir sind in Knoten v und erkunden die Nachbarschaft.
        for(int e = 0; e < E[v].size(); e++) {
                int w = E[v][e];
                // Nun prüfen wir ob der Nachbar w noch unbesucht ist.
                if(!visited[w]) {
                        visited[w] = true;
                        dfs(w);
                }
        }
}

int main() {
        // Wir beginnen damit E einzulesen, z.B. so:
        int n, m;
        cin >> n >> m;
        E = vector<vector<int>>(n);
        for(int i = 0; i < m; i++) {
                int a, b;
                cin >> a >> b;
                E[a].push_back(b);
                E[b].push_back(a);
        }
        // Nun können wir unsere Tiefensuche starten
        int start = 0;
        visited = vector<int>(n, false); // Zu Beginn haben wir noch nichts besucht.
        visited[start] = true;
        dfs(start);
        // Ob der Ausgang erreicht werden kann, können wir nun ganz leicht ablesen.
        cout << "Kann der Ausgang erreicht werden?\n";
        if(visited[n-1]) {
                cout << "Ja!\n";
        } else {
                cout << "Nein!\n";
        }
}

Und wozu ist das gut?

Eine solche Tiefensuche kann uns also beantworten, ob zwei Knoten direkt oder indirekt verbunden sind oder nicht. Die Menge aller Knoten, die gegenseitig miteinander verbunden sind, nennt man auch Zusammenhangskomponente. Der Graph in Bild 1 besteht aus zwei solchen Zusammenhangskomponenten. Die Knoten 1 bis 4 bilden die eine, die Knoten 5 und 6 die andere Komponente. Um alle Zusammenhangskomponenten mittels Tiefensuche zu bestimmen, gehen wir einmal durch alle Knoten und starten bei jedem noch unbesuchten Knoten eine Tiefensuche. Jedesmal wenn wir eine neue Tiefensuche starten, entdecken wir eine neue Komponente.

Eine weitere nützliche Anwendung ist das Zweifärben von Graphen. Wir möchten dabei jeden Knoten eines Graphen entweder rot oder blau einfärben, sodass keine zwei benachbarten Knoten dieselbe Farbe bekommen. Ist das immer möglich? Nein. In einem Dreieck geht das beispielsweise nicht. Wenn du dir das ein wenig genauer überlegst, siehst du, dass eine gültige Zweifärbung genau dann möglich ist, wenn der Graph keinen Zyklus ungerader Länge enthält, es also keinen Weg gibt, der nach einer ungeraden Anzahl Schritte wieder bei seinem Startpunkt angelangt.

Der Graph in Bild 1 ist nicht zweifärbbar, da das Dreieck 2 − 3 − 4 eine Zweifärbung verunmöglicht. Bild 2 zeigt dir einen zweifärbbaren Graphen.

2H DFS bicoloring graph example

Bild 2: Ein Beispiel eines zweifärbbaren Graphen, der aus zwei Zusammenhangskomponenten besteht.

Eine Art eine solche Färbung zu finden (oder herauszufinden, dass es gar keine solche gibt) ist mittels Tiefensuche. Wenn wir den Startknoten rot markieren, dann müssen alle seine Nachbarn blau sein und alle deren Nachbarn wieder rot und so weiter. Sobald wir also die Farbe des Startknotens wählen, ist die Färbung für die gesamte Zusammenhangskomponente fixiert. Die Tiefensuche erlaubt uns nun diese Färbung zu simulieren und gleichzeitig zu überprüfen, ob es irgendwo zu einem Konflikt kommt, also zu zwei gleichgefärbten, benachbarten Knoten. In der Implementierung ersetzen wir dazu einfach “visited” durch “color”, wobei wir 0 für ungefärbt, 1 für rot und 2 für blau stehen lassen. Innerhalb der DFS-Schleife prüfen wir dann:

bool dfs(int v) {
        // Wir sind in Knoten v und erkunden die Nachbarschaft.
        for(int e = 0; e < E[v].size(); e++) {
                int w = E[v][e];
                // Nun prüfen wir ob der Nachbar w noch unbesucht ist.
                if(color[w]==0) {
                        // Setze w auf die andere Farbe als v.
                        color[w] = 3-color[v];
                        // Rekursiere und brich ab, sobald ein Fehler gefunden wurde:
                        if(!dfs(w)) {
                                return false;
                        }
                } else {
                        // Prüfe, dass v und w unterschiedliche Farbe haben.
                        if(color[v] == color[w]) {
                                // Der Graph ist in diesem Fall nicht zweifärbbar, was wir beispielsweise mit dem Rückgabewert mitteilen können.
                                return false;
                        }
                }
        }
        return true;
}

Aufgabe

Gegeben ein ungerichteter, ungewichteter Graph, entscheide ob es möglich ist, seine Knoten mit zwei Farben zu färben, sodass keine zwei benachbarten Knoten die selbe Farbe erhalten.

Eingabe

Auf der ersten Zeile steht die Zahl T, die Anzahl Testfälle. Es folgen T Graphenbeschreibungen mit jeweils dem folgenden Format: Auf der ersten Zeile steht n und m, die Anzahl Knoten und Kanten. Anschliessend folgen m Zeilen, welche die m Kanten mittels je zweier nullbasierter Indices beschreiben. Eine Zeile mit a und b bedeutet, dass der Knoten a mit Knoten b verbunden ist (und umgekehrt). Beachte, dass die Knoten nullbasiert indexiert sind. Sie sind also von 0 bis n − 1 nummeriert.

Ausgabe

Gib für den t-ten Testfall “Case #t:” aus, gefolgt von “YES” oder “NO”, je nachdem ob der t-te Graph zweifärbbar ist oder nicht.

Limits

  • T = 100
  • N ≤ 1 000
  • M ≤ 10 000

Beispiele

Eingabe:

1
6 5
0 2
1 2
1 3
2 3
4 5

Ausgabe:

Case #1: NO

Bemerkung:

Das ist der Graph aus Bild 1. Das Dreieck 1 − 2 − 3 − 1 verunmöglicht eine Zweifärbung.

Eingabe:

1
7 6
0 1
2 1
5 3
4 3
4 6
5 6

Ausgabe:

Case #1: YES

Bemerkung:

Bild 3 zeigt dir diesen Graph und eine mögliche, gültige Färbung mit zwei Farben.
DFS bicoloring second example

Bild 3: Der zweifärbbare Graph des zweiten Beispiels.

Anmerkung: Eine Anwendung dieses Zweifärbeproblems war die erste Hälfte der Aufgabe “River” der ersten Runde der SOI 2015. Du kannst die Aufgabe hier nachlesen und du findest hier die Lösungsbeschreibung.

Zögere nicht, uns Fragen zu dieser Aufgabe, der Programmierung oder der Webseite per E-Mail (info@soi.ch) zu stellen.

Breitensuche

Der Unterschied zwischen der Tiefensuche, welche wir im vorhergehenden Tutorial kennengelernt haben, und der Breitensuche, die wir jetzt anschauen werden, ist ein kleiner aber feiner. Abgekürzt wir die Breitensuche oft einfach mit BFS (für das Englische breadth first search).

Problembeschreibung

Wie wir gesehen haben, erlaubt uns die Tiefensuche die Zusammenhangskomponenten eines Graphen zu bestimmen oder ihn mit zwei Farben zu färben. Was wir aber bisher noch nicht können, ist das Finden von kürzesten Wegen zwischen zwei Knoten. Die Breitensuche wird uns dies ermöglichen.

Standardalgorithmus

Breitensuche - Woher kommt der Name?

In der Tiefensuche stürzten wir uns Hals über Kopf in die Tiefe des Graphen. Wir schlugen einfach mal eine willkürliche Richtung ein und gingen so lange weiter bis wir umkehren mussten, weil wir nichts Neues mehr entdecken konnten. Erst dann schauten wir uns nach möglichen alternativen Abzweigungen um.

Die Breitensuche geht nun - wie der Name suggeriert - zuerst in die Breite statt in die Tiefe. Wir wollen zuerst alles erkunden, was unmittelbar zum Startpunkt benachbart ist. Erst danach schauen wir uns Knoten mit Distanz 2 an, also die Nachbarn der Nachbarn. Und erst wenn wir alle diese Nachbarn zweiten Grades besucht haben, dann erst beginnen wir mit den Nachbarn der Nachbarn der Nachbarn. Und so weiter.

Algorithmus: Breitensuche

Diese Idee lässt sich am einfachsten mit Hilfe einer Warteschlange (Englisch queue) implementieren. Darin merken wir uns alle Knoten, die wir entdeckt haben, deren Nachbarn wir uns aber noch anschauen wollen.

Bei der Tiefensuche erfolgten diese zwei Schritte jeweils unmittelbar hintereinander, also sobald wir einen Knoten entdeckt haben, haben wir auch gleich damit begonnen seine Nachbarn anzuschauen. Das hat uns erlaubt, die Tiefensuche mittels Rekursion zu implementieren. Nun wollen wir aber für die Breitensuche, dass wir zuerst alle Nachbarn ersten Grades anschauen, bevor wir den ersten Nachbarn zweiten Grades anschauen. Die Warteschlange simuliert nun dieses “Hinten-Anstellen-und-Warten” der neu entdeckten Knoten. In C++ kann das dann etwa so aussehen:

// Wir nehmen wieder an, dass E eine nullbasierte Adjazenzliste darstellt.
vector<vector<int>> E;
vector<int> visited;

void bfs(int start) {
        queue<int> Q; // Die Warteschlange für die neu entdeckten Knoten.
        Q.insert(start);
        while(!Q.empty()) {
                int v = Q.front();
                Q.pop();
                // Wir sind in Knoten v und erkunden die Nachbarschaft.
                for(int e = 0; e < E[v].size(); e++) {
                        int w = E[v][e];
                        // Nun prüfen wir, ob der Nachbar w noch unbesucht ist.
                        if(!visited[w]) {
                                visited[w] = true;
                                // Anstelle des rekursiven Aufruf der DFS,
                                // fügen wir w nun lediglich in die Schlange ein.
                                Q.insert(w);
                        }
                }
        }
}

int main() {
        // Graph einlesen, wie zuvor.
        ...
        // Nun können wir die Breitensuche starten
        int start = 0;
        visited = vector<int>(n, false); // Zu Beginn haben wir noch nichts besucht.
        visited[start] = true;
        bfs(start);
        // In visited[] können wir nun wiederum ablesen, ob
        // ein bestimmter Knoten erreicht werden kann.
}

Bild 1 zeigt dir an einem Beispiel wie sich die Besuchsreihenfolge der Knoten in einer Breitensuche und einer Tiefensuche unterscheiden können.

2H BFS example

Bild 1: Die Breitensuche (links) und Tiefensuche (rechts) auf dem selben Graphen. Die Zahlen geben die Entdeckungsreihenfolge der Knoten an und die Pfeile bezeichnen die Kanten entlang welcher die Knoten entdeckt wurden.

Kürzeste Wege

Für ungerichtete, ungewichtete Graphen erlaubt uns die Breitensuche die Länge des kürzesten Weges zwischen dem Startpunkt und jedem beliebigen anderen Knoten zu bestimmen. Die Länge eines Pfades messen wir in der Anzahl Kanten, denen wir entlanggehen. Ungewichtet heisst hier also, dass jede Kante als gleich lang gezählt wird. Falls die Kanten unterschiedliche Länge haben, genügt die Breitensuche nicht mehr, um den kürzesten Weg zu berechnen. Der Algorithmus von Dijkstra, welcher dir in einer anderen Aufgabe erklärt wird, löst aber genau dieses Problem. Aber wie berechnen wir nun die ungewichtete Länge des kürzesten Weges von a nach b mit Hilfe der Breitensuche?

Die Erkundungsreihenfolge der BFS hat die schöne Eigenschaft, dass wir die Knoten in aufsteigender Distanz zum Startknoten besuchen. Das heisst, alle Knoten mit Distanz 5 besuchen wir unmittelbar nach den Knoten mit Distanz 4 und umittelbar vor den Knoten mit Distanz 6. Wenn immer wir also einen neuen Knoten entdecken, können wir dessen Distanz zum Start direkt bestimmen, nämlich als die Distanz zum aktuellen Knoten plus 1.

In der Implementierung von oben können wir dies einbauen, indem wir zum Beispiel einen Vektor dist hinzufügen, den wir für jeden Knoten mit unendlich initialisieren (oder einfach einer fixen, sehr grossen Zahl) und dann dist[start] auf Null setzen. Die Distanz der neu entdeckten Knoten setzen wir dann hier mit einer einzigen neuen Zeile:

...
if(!visited[w]) {
        visited[w] = true;
        // Anstelle des rekursiven Aufruf der DFS,
        // fügen wir w nun lediglich in die Schlange ein.
        Q.insert(w);
        dist[w] = dist[v] + 1; // Neue Zeile!
}
...

Bild 2 zeigt nochmals denselben Graphen aber jetzt mit den Distanzangaben zwischen den Knoten und dem Start.

2H BFS example

Bild 2: Die Distanzen nach einer Breitensuche, die beim obersten Knoten begonnen hat.

Aufgabe

Du sollst nun diese Breitensuche implementieren, um die Distanz zwischen dem ersten und letzten Knoten eines Graphens zu bestimmen.

Eingabe

Auf der ersten Zeile steht die Zahl T, die Anzahl Testfälle. Es folgen T Graphenbeschreibungen mit jeweils dem folgenden Format: Auf der ersten Zeile steht n und m, die Anzahl Knoten und Kanten. Anschliessend folgen m Zeilen, welche die m Kanten mittels je zweier nullbasierter Indices beschreiben. Eine Zeile mit a und b bedeutet, dass der Knoten a mit Knoten b verbunden ist (und umgekehrt). Beachte, dass die Knoten nullbasiert indexiert sind. Sie sind also von 0 bis n − 1 nummeriert.

Ausgabe

Gib für den t-ten Testfall “Case #t:” aus, gefolgt von einer Zahl, die Länge des kürzesten Weges von Knoten 0 zu Knoten n − 1 im t-ten Graphen. Die Eingaben sind so gewählt, dass es immer ein Weg zwischen diesen beiden Knoten gibt.

Limits

  • T = 100
  • N ≤ 1 000
  • M ≤ 10 000

Beispiel

Eingabe:

2
7 8
0 1
2 0
0 3
1 4
2 4
5 3
4 6
6 5
7 7
0 1
2 1
2 0
4 0
4 3
5 3
5 6

Ausgabe:

Case #1: 3
Case #2: 4

Bemerkung:

Bild 3 zeigt dir diesen Graphen. Es ist der selbe Graph wie auf den Bildern 1 und 2.
2H BFS example

Bild 3: Illustration des ersten Beispiels.

Zusatzaufgabe: Überlege dir, wie du nicht nur die Länge des Weges sondern auch einen kürzesten Weg (als Abfolge von Knoten) ausgeben kannst.

Zögere nicht, uns Fragen zu dieser Aufgabe, der Programmierung oder der Webseite per E-Mail (info@soi.ch) zu stellen.

Dijkstra

Mit Breitensuche lassen sich kürzeste Wege in Graphen finden, solange alle Kanten gleich lang sind. Häufig ist das jedoch nicht der Fall: Es kann zum Beispiel unterschiedlich lange dauern, von A nach B zu gelangen, wie von C nach D zu gelangen, obwohl es direkte Kanten von A nach B, sowie von C nach D gibt. In solchen Fällen geben wir jeder Kante zusätzlich ein Gewicht, welches diese zusätzliche Information beinhaltet.

In dieser Aufgabe geht es um Dijkstras Algorithmus zur Bestimmung von kürzesten Wegen in gerichteten Graphen mit nichtnegativen Kantengewichten.

Problembeschreibung

Gegeben ist ein gerichteter gewichteter Graph G = (V, E), das heisst einige Knoten v ∈ V, welche durch Pfeile/Kanten e ∈ E verbunden sind, wobei jeder Kante eine Zahl zugeordnet wird, ihr Kantengewicht. Wir stellen Kanten als Tupel e = (u, v, w) dar, wobei u und v die Anfangs- und Endknoten der Kante sind und w das Kantengewicht ist. Ein Weg von s nach t ist eine Reihe von Kanten (s, k2, w1), (k2, k3, w2), (k3, k4, w3), …, (kn − 2, kn − 1, wn − 2), (kn − 1, t, wn − 1). Das heisst, wenn man bei s beginnt und dann der Reihe nach den Kanten folgt, erreicht man Knoten t. Die Länge des Weges ist durch die Summe aller Kantengewichte gegeben: w1 + w2 + ⋯ + wn − 1. Ein kürzester Weg von s nach t ist ein Weg von s nach t dessen Länge kleinstmöglich ist.

Wir wollen nun die Länge des kürzesten Weges zwischen zwei gegebenen Knoten bestimmen. Dies wird deine Aufgabe sein. Dijkstras Algorithmus kann verwendet werden, um dieses Problem effizient zu lösen, gegeben dass alle Kantengewichte mindestens 0 sind.

(Dijkstras Algorithmus löst eigentlich sogar ein noch allgemeineres Problem: Er findet für einen gegebenen Startpunkt u kürzeste Wege zu allen anderen Knoten. Er kann natürlich auch verwendet werden um für einen gegebenen Endpunkt v kürzeste Wege von allen anderen Knoten her zu finden.)

Dijkstras Algorithmus

Sei SP(s, t) die Länge des kürzesten Weges zwischen s und t. Eine Eigenschaft von kürzesten Wegen ist, dass

SP(s, t) = 0, 

SP(s, t) = min(t’, t, w) ∈ E SP(s, t’) + w für s ≠ t

Hier machen wir einfach eine Fallunterscheidung über die letzte Kante auf dem kürzesten Pfad von s nach t. Falls eine gegebene Kante (t’, t, w) die letzte Kante auf dem kürzesten Weg von s nach t ist, dann ist SP(s, t) einfach SP(s, t’) + w. SP(s, t) ist dann die kleinste dieser Möglichkeiten.

Wir definieren SP(s, t) = ∞ falls es gar keinen Weg von s nach t gibt.

Für Graphen, die keine Wege von einem Knoten zu sich selbst haben, definieren die obigen Gleichungen bereits einen funktionierenden Algorithmus für die Berechnung von kürzesten Wegen, weil es keine zyklischen Abhängigkeiten zwischen Werten von SP gibt.

Im Allgemeinen gibt es aber solche zyklische Abhängigkeiten.

Dijkstras Algorithmus löst dieses Problem, in dem er für ein gegebenes s für alle t die Werte von SP(s, t) in aufsteigender Reihenfolge berechnet. Es kann dabei dann natürlich vorkommen, dass nicht für jedes mögliche t (in der zweiten Gleichung oben) der Wert SP(s, t’) bereits bekannt ist. Allerdings spielen diese Werte SP(s, t’) dann natürlich keine Rolle, weil sie wegen der geschickt gewählten Reihenfolge mindestens so gross sind wie SP(s, t). Hier verwenden wir die Annahme, dass alle w mindestens 0 sind.

Während jedem Zeitpunkt in der Ausführung von Dijkstras Algoritmus gibt es also einige Knoten t für die wir SP(s, t) bereits kennen, die bekannten Knoten und einige Knoten, für die dieser Wert noch nicht bekannt ist, die unbekannten Knoten. Ausserdem wissen wir, dass alle unbekannten Werte mindestens so gross sind wie jeder bekannte Wert.

Für jeden unbekannten Wert SP(s, t) gibt es dann drei Möglichkeiten:

  1. SP(s, t) = SP(s, t’) + w für (t’, t, w) ∈ E und SP(s, t’) ist bekannt.
  2. SP(s, t) = SP(s, t’) + w für (t’, t, w) ∈ E und SP(s, t’) ist unbekannt.
  3. SP(s, t) = ∞. (Falls t von s aus gar nicht erreichbar ist.)

(Merke, dass Möglichkeiten 1. und 2. sich nicht gegenseitig ausschliessen. Wieso?)

Dijkstras Algorithmus berechnet für alle (t’, t, w) ∈ E mit bekanntem SP(s, t’) und unbekanntem SP(s, t) den Wert SP(s, t’) + w als möglichen Kandidaten für den Wert von SP(s, t).

Die zentrale Beobachtung ist, dass der kleinste Kandidatenwert über alle solchen (t’, t, w) tatsächlich der korrekte Wert für das entsprechende SP(s, t) ist.

(Das sollte intuitiv klar sein. Falls nicht, hier ein Beweis:

Es reicht zu zeigen, dass falls es erreichbare unbekannte Knoten gibt, es für mindestens einen unbekannten Knoten t mit minimalem SP(s, t) gelten muss, dass ein kürzester Weg zu ihm von einem bekannten Knoten aus über eine einzige Kante geht.

Beweis: Nimm an, dass die Behauptung nicht stimmt. Für jeden unbekannten Knoten hat mindestens ein kürzester Weg von s zu ihm genau eine Kante zwischen bekannten und unbekannten Knoten. Schaue einen unbekannten Knoten t mit minimalem SP(s, t) an für den einer der solchen kürzesten Wege p die kleinste Anzahl Kanten zwischen unbekannten Knoten hat. Nach Annahme gibt es auf dem Weg mindestens eine solche Kante. Sei t der zweitletzte Knoten auf dem gewählten Weg. Dann ist SP(s, t’) ≤ SP(s, t) und ein kürzester Weg von s nach t hat weniger Kanten zwischen Knoten mit unbekannten Werten als p, ein Widerspruch.)

Dijkstras Algorithmus funktioniert wie folgt:

  • Führe einen Kandidatenwert 0 für Knoten s ein.
  • Solange es noch Kandidatenwerte gibt:
    • Setze SP(s, t’) = c für den kleinsten Kandidatenwert c, so dass t der zugehörige Knoten ist, sowie SP(s, t’) noch nicht bekannt ist.
    • Immer dann wenn ein neuer Wert SP(s, t’) bekannt wird, berechne Kandidatenwerte SP(s, t’) + w für alle t mit (t’, t, w) ∈ E.

Es folgt eine Implementierung in C++11:

#include <queue>
using namespace std;

#define OG(T) bool operator>(const T& o)const
struct E{ int t,w; OG(E){ return w>o.w; } };
using VE=vector<E>;
struct V{ VE in; bool v; };
using VV=vector<V>;
using HE=priority_queue<E,VE,greater<E>>;

int dijkstra(VV& g,int s,int t){
    HE q; q.push({s,0});
    while(!q.empty()){
        E c=q.top(); q.pop();
        if(g[c.t].v) continue;
        g[c.t].v=1;
        if(c.t==t) return c.w;
        for(auto&e:g[c.t].in)
            q.push({e.t,c.w+e.w});
    }
    return -1;
}

Der Graph wird dargestellt als ein vector<V>, wobei eine Instanz von V einen einzelnen Knoten beschreibt: in ist ein vector<E> mit allen ausgehenden Kanten. v ist ein bool, welcher speichert, ob der Knoten bereits bekannt ist oder nicht. Eine Instanz von E beschreibt den Zielknoten t sowie das Kantengewicht w.

Wir verwenden eine priority_queue um die Menge der Kandidatenwerte zu verwalten. (Merke, dass die eingebaute priority_queue dummerweise standardmässig den grössten Wert zurückgibt anstatt den kleinsten.)

  • q.push({s,0}) startet die Berechnung indem der Kandidatenwert 0 für Knoten s eingeführt wird.
  • if(g[c.t].v) continue; verhindert, dass bereits bekannte Werte überschrieben werden. (Das ist notwendig. Wieso?)
  • if(c.t==t) return c.w; gibt das Resultat aus, falls der Zielknoten gefunden wurde. An dieser Stelle könnte man z.B. auch die Werte von SP speichern.
  • for(auto&e:g[c.t].in) geht über alle Kanten, die vom aktuellen Knoten weggehen.
  • q.push({e.t,c.w+e.w}); führt neue Kandidatenwerte ein.
  • In return -1; steht -1 für , also dafür, dass es keinen Weg von s nach t gibt.

Die Laufzeit dieser Version von Dijkstras Algorithmus ist O(MlogN), wobei N die Anzahl Knoten und M die Anzahl Kanten ist.

Aufgabe

Gegeben mehrere gerichtete Graphen mit nicht-negativen Kantengewichten, finde jeweils die Länge des kürzesten Weges vom ersten zum zweiten Knoten.

Eingabe

Auf der ersten Zeile steht die Zahl T, die Anzahl Testfälle. Es folgen T Zeilen mit jeweils den ganzen Zahlen N, M, sowie M Trippeln von ganzen Zahlen u v w (1 ≤ u, v ≤ N, 0 ≤ w ≤ 1000), welche Kanten von u nach v mit Gewicht w beschreiben. Die Knoten sind von 1 bis N durchnummeriert.

Die Zahlen sind durch jeweils ein oder zwei Leerzeichen getrennt (siehe Beispiel).

Ausgabe

Gib für den t-ten Testfall “Case #t:” aus, gefolgt von der Länge des kürzesten Weges von Knoten 1 zu Knoten 2. Falls es von Knoten 1 zu Knoten 2 keinen Weg gibt, gib “Infinity” aus.

Limits

  • T = 100
  • 2 ≤ N ≤ 1 000
  • 0 ≤ M ≤ 10 000

Beispiel

Eingabe:

3
3 2  1 3 5  3 2 7
3 3  1 2 7  1 3 4  3 2 1
3 1  1 3 4

Ausgabe:

Case #1: 12
Case #2: 5
Case #3: Infinity

Zögere nicht, uns Fragen zu dieser Aufgabe, der Programmierung oder der Webseite per E-Mail (info@soi.ch) zu stellen.

Binäre Suche

Problem

Gegeben sei eine sortierte Liste A von N Zahlen (a1, a2, …, aN). Wir wollen nun herausfinden, ob eine bestimmte Zahl X in dieser Liste vorhanden ist. Falls X in der Liste vorhanden ist, wollen wir zusätzlich die Position bestimmen.

Die triviale Lösung, die jede Position der Liste mit X vergleicht, hat eine Laufzeit von O(N) (Diese funktioniert jedoch auch bei unsortieren Listen, wo die binäre Suche fehlschlägt). Mit der binären Suche können wir das Problem jedoch in O(logN) lösen.

Lösung

Der Algorithmus der binären Suche ist Greedy und funktioniert nach dem Prinzip Teile und Herrsche.

Die folgenden Schritte wiederholen wir, bis die gesuchte Zahl X gefunden wurde oder die Liste leer ist:

  1. Wir vergleichen die Zahl B = ai (mit i = ⌊(N)/(2), wobei ⌊⋅⌋ für abrunden steht) in der Mitte der Liste mit X, dabei können folgende Fälle auftreten:
    • B = X: Die Zahl ist gefunden. Wir können die Position berechnen und zurück geben.
    • B > X: Da X kleiner ist als B, muss X vor B sein, falls es in der Liste vorkommt. Wir können uns also auf die linke Hälfte beschränken.
    • B < X: Analog zum vorigen Fall können wir uns in diesem Fall auf die rechte Hälfte beschränken.
  2. Ist die neue Liste leer, kommt X nicht in der Liste vor. Andernfalls beginnen wir mit der nun halbierten Liste wieder bei 1.

Am einfachsten schränken wir dazu die Liste durch einen oberen (O) und unteren (U) Index ein, die wir dann iterativ anpassen:

Seien A, N, X gegeben
Setze U = 1, O = N
Setze I = U+(O-U)/2
Solange U != O und  A[I] != X
  Falls A[I] > X
    Setze O = I-1
  Falls A[I] < X
    Setze U = I+1
  Setze I = U+(O-U)/2
Falls A[I] = X
  "X ist an Position I in A"
Sonst
  "X ist nicht in A"

Aufgabe

Gegeben eine monotone diskrete Funktion P und ein y-Wert Y, finde den zu Y gehörigen x-Wert X.

P(x) = A*x1 ⁄ 4 + B*x1 ⁄ 3 + C*x1 ⁄ 2 + D*x + E*x2 + F*x3 + G*x4 mit dem Definitionsbereich D = {x ∈ ℕ∣1 ≤ x ≤ N}

Monoton bedeutet, dass die Werte der Funktion immer steigen (d.h. wenn man nach rechts geht, werden die Werte immer grösser). Die gegebene Funktion ist in jedem Fall monoton.

Wir betrachten nur diskrete Werte von P, das heisst die abgerundeten Funktionswerte.

Werte von Funktionen berechnen

Wollen wir den Wert einer Funktion P(x) = 2*x1 ⁄ 2 + 3*x + 2*x2 an einer bestimmten Stelle, z.B. x = 4 berechnen, so setzen wir einfach den Wert (4) für x ein und rechnen aus:

P(4) = 2*41 ⁄ 2 + 3*4 + 2*42 = 2*2 + 3*4 + 2*16 = 4 + 12 + 32 = 48

Beachte dass x1 ⁄ n die n-te Wurzel von x ist: x1 ⁄ n = n(x).

In Computerprogrammen geht das ausrechnen sehr einfach. Wir schreiben einfach eine Funktion, die den Wert ausrechnet, in C++ z.B. so:

double P(double x) {
    return 2*pow(x, 1.0/2) + 3*x + 2*pow(x, 2);
}

Hinweis: die Funktion pow befindet sich in math.h. Beachte auch, dass du 1.0 ⁄ 2 schreiben solltest und nicht 1 ⁄ 2. 1 ⁄ 2 ist 0, denn die Division rundet bei Integern ab. Da 1.0 ein Double ist, wird die Division mit Nachkommastellen durchgeführt.

Hinweis: die Funktion pow befindet sich in math.h.

Eingabe

Auf der ersten Zeile steht eine ganze Zahl T, die Anzahl Testfälle. Für jeden Testfall folgt eine Zeile mit jeweils den Zahlen N, A, B, C, D, E, F, G, Y. Hierbei stehen:

  • N (Ganzzahl) für die obere Schranke des zu betrachtenden Definitionsbereichs von P, die untere Schranke ist immer 1,
  • A, B, C, D, E, F, G (Fliesskommazahlen) für die Koeffizienten der monotonen diskreten Funktion P,
  • Y (Ganzzahl) für den gesuchten Funktionswert.

Ausgabe

Für den t-ten Testfall gib eine Zeile “Case #t: X”, wobei X ein zu Y gehöriger x-Wert, oder 0, falls die Funktion P den Wert Y im vorgegebenen Bereich nicht annimmt.

Limits

  • T = 100
  • N ≤ 10000000
  • 0 ≤ A, B, C, D, E, F, G ≤ 1000
  • Y ≤ P(N)

Beispiel

Eingabe:

2
10 0 0 0 0 1 0 0 4
10 0 0 0 0 1 0 0 6

Ausgabe:

Case #1: 2
Case #2: 0

Bemerkung:

Die Funktion im Beispiel ist P(x) = x2. Im ersten Fall ist P(2) = 4. Aber für kein ganzzahliges x wird P(x) = 6.

Zögere nicht, uns Fragen zu dieser Aufgabe, der Programmierung oder der Webseite per E-Mail (info@soi.ch) zu stellen.

Präfixsumme

Problem

Es ist ein grosses M × N Rechteck von Zahlen gegeben. Nun sollen für Q verschiedene Teilrechtecke die Summe aller Zahlen in diesem Teilrechteck berechnet werden. Betrachten wir zunächst den eindimensionalen Fall, bei dem man nur eine Liste mit N Zahlen hat. Der offensichtliche Ansatz wäre, für jeden gefragten Bereich die einzelnen Zahlen zu addieren, also etwas in der Art:

for range in ranges:
  sum = 0
  for i in range(range.start, range.end):
    sum += list_of_numbers[i]
  print(sum)

Dies ist jedoch für viele Anfragen zu langsam, da jede der Q Abfragen bis zu N Operationen benötigt, der Algorithmus also in O(NQ) läuft.

Lösung

Statt für jede Abfrage viel zu berechnen, erstellen wir zu Beginn eine zweite Hilfsliste, die vorberechnete Werte enthält. Diese Werte erlauben uns dann, jede der Abfragen in konstanter Zeit (O(1)) zu beantworten. Da wir die Berechnung der Hilfsliste nur einmal durchführen müssen, ist die Gesamtlaufzeit somit viel besser.

Nennen wir unsere Liste A mit den Elementen a1, a2, a3, …, aN. Wenn wir nun unsere Hilfsliste - nennen wir sie B mit den Elementen b1, b2, b3, …, bN - so berechnen, dass in bi gerade die Summe aller Zahlen der Liste A bis und mit i drin stehen, können wir die Summe des Bereichs von i (inklusive) bis j (inklusive) mit bj − bi − 1 berechnen. Warum ist dies so?

Schauen wir uns z.B. den Bereich 3 − 6 an. Die Summe die wir berechnen wollen ist also a3 + a4 + a5 + a6. Dann ist b6 = a1 + a2 + a3 + a4 + a5 + a6 und b2 = a1 + a2. Rechnen wir nun b6 − b2, so ergibt dies b6 − b2 = (a1 + a2 + a3 + a4 + a5 + a6) − (a1 + a2) = a1 − a1 + a2 − a2 + a3 + a4 + a5 + a6 = a3 + a4 + a5 + a6. Dies ist genau die Summe, die wir suchen. Wir können also durch die Subtraktion die zu viel hinzuaddierten Elemente wieder “entfernen”.

Liste A Liste B 5 1 2 4 9 7 5 3 4 8 6 5 6 8 12 21 28 33 36 40 48 54 = - 28 36 8

Implementieren kann man das z.B. folgendermassen:

# vorberechnen
b = [a[0]]
for i in a[1:]:
  b.append(b[-1] + i)

# Abfragen
for range in ranges:
  if range.start == 0:
    print(b[range.end])
  else:
    print(b[range.end] - b[range.start-1])

Das Vorberechnen können wir in O(NM) durchführen und alle Abfragen in O(Q) (da jede Abfrage in konstanter Zeit beantwortet werden kann). Somit verbessert sich unsere Lösung von O(NMQ) auf O(NM + Q).

Diese Idee kann nun einfach auf den zweidimensionalen Fall erweitert werden.

Ist nun A das gegebene Rechteck mit Zahlen, so füllen wir das vorberechnete Rechteck B jeweils mit der Summe des Teilrechtecks von der oberen linken Ecke bis zum aktuellen Feld. Dies kann man auf verschiedene Arten effizient berechnen. Eine Möglichkeit ist, das Rechteck von oben links durchzugehen und jeweils by, x = by − 1, x + by, x − 1 − by − 1, x − 1 zu setzen. Die Subtraktion wird benötigt, da wir sonst dieses Teilrechteck doppelt zählen würden.

Nun kann die Summe des Teilrechtecks von (ix ⁄ iy) bis (jx ⁄ jy) ausgerechnet werden mit bjy, jx − biy − 1, jx − bjy, ix − 1 + biy − 1, ix − 1. Wir nehmen also wieder den zu grossen Bereich, der bis (jx ⁄ jy) geht. Anschliessend ziehen wir den linken Bereich sowie den oberen Bereich ab, den wir zu viel hinzugezählt haben. Nun haben wir den Bereich bis (ix − 1 ⁄ iy − 1) jedoch zweimal abgezogen, weshalb wir ihn wieder hinzuaddieren.

= - - +

Eingabe

Auf der ersten Zeile steht eine ganze Zahl T, die Anzahl Testfälle. Für jeden Testfall folgen:

  • eine Zeile mit N M Q, die Anzahl Spalten, Anzahl Zeilen und Anzahl Abfragen.
  • eine Zeile mit f0 af cf mf. Dies definiert eine Folge mit fi + 1 = (fiaf + cf) mod mf. Die Folge startet beim gegebenen f0.
  • eine Zeile mit h0 ah ch mh. Dies definiert eine Folge mit hi + 1 = (hiah + ch) mod mh. Die Folge startet beim gegebenen h0.

Das M × N Rechteck ist nun gegeben durch ay, x = fyN + x.

Die Q Abfragen sind gegeben durch rsx, rsy, rex, rey, gesucht ist jeweils die Summe der Zahlen im Rechteck zwischen den Eckpunkten (rsx ⁄ rsy) und (rex ⁄ rey), jeweils inklusive. Für die Abfrage q (0 ≤ q < Q) gilt rsx = min(hq⋅4 + 0  mod N, hq⋅4 + 1  mod N), rex = max(hq⋅4 + 0  mod N, hq⋅4 + 1  mod N), rsy = min(hq⋅4 + 2  mod M, hq⋅4 + 3  mod M) und rey = max(hq⋅4 + 2  mod M, hq⋅4 + 3  mod M).

Die etwas komplizierte Eingabe verwenden wir, damit du nicht riesige Mengen an Daten herunterladen musst. Du kannst folgenden Code für C++ verwenden, um die Zahlen zu generieren:

struct range{
  int startX, startY, endX, endY;

  range(int sx, int sy, int ex, int ey) : startX(sx), startY(sy), endX(ex), endY(ey){}
};

void readInput(int& N, int&M, int& Q, vector<vector<int> >& field, vector<range>& queries){
  cin >> N >> M >> Q;
  field.clear();
  field.resize(M, vector<int>(N));
  queries.clear();

  int f0, a, c, m;

  cin >> f0 >> a >> c >> m;
  for(int y = 0; y < M; y++){
    for(int x = 0; x < N; x++){
      field[y][x] = f0;
      f0 = (f0 * a + c) % m;
    }
  }

  cin >> f0 >> a >> c >> m;
  for(int q = 0; q < Q; q++){
    int r[4];
    for(int i = 0; i < 4; i++){
      r[i] = f0;
      f0 = (f0 * a + c) % m;
    }
    queries.push_back(range(min(r[0]%N, r[1]%N), min(r[2]%M, r[3]%M), max(r[0]%N, r[1]%N), max(r[2]%M, r[3]%M)));
  }
}

// in your code
int N, M, Q;
vector<vector<int> > field;
vector<range> queries;
readInput(N, M, Q, field, queries);

Ausgabe

Gib für jeden Testfall eine Zeile mit “Case #t:” aus (t ist die Nummer des Testfalls), gefolgt von Q leerzeichengetrennte Zahlen si, die Summe der Zahlen in des Teilrechtecks i.

Limits

  • 1 ≤ N, M ≤ 103
  • 1 ≤ Q ≤ 106
  • 0 < fi, af, cf, mf ≤ 109
  • 0 ≤ ay, x ≤ 109
  • 0 ≤ rsx ≤ rex < N
  • 0 ≤ rsy ≤ rey < M

Beispiele

Eingabe:

2
7 2 7
67 56 86 101
62 34 71 71
5 3 8
31 28 65 79
2 15 48 79

Ausgabe:

Case #1: 298 216 140 290 445 86 126
Case #2: 40 493 277 275 339 372 151 129

Zögere nicht, uns Fragen zu dieser Aufgabe, der Programmierung oder der Webseite per E-Mail (info@soi.ch) zu stellen.

Versuche

# Aufgabe Subtask Punktzahl Verdikt

Rangliste

RanglisteBenutzernameTotal (100)dfs (20)bfs (20)dijkstra (20)bsearch (20)prefixsum (20)
loading ...