Module: Brücken. Gelenkpunkte


Problem

2/4

Suchen nach Brücken und Gelenkpunkten

Theory Click to read/hide

WAHL
Die Brücke ist eine solche Rippe in der Reihe, in der die Anzahl der Verbindungen zunimmt.
Beispiel 1

Beispiel 2

Blau wird durch Rippen, unterschiedliche Farben, verschiedene Kommunikationskomponenten, die nach dem Entfernen der Bänder gebildet werden, markiert.

Die Böden in der Reihe können nach O(m*(n + m) gesucht werden, nämlich alle Rippen zu überqueren und die Reihe zu umgehen, in der wir nicht durch die eingezogene Rippe gehen und die Anzahl der Verbindungen zählen. Mit ihrer Erhöhung des relativen Rings werden wir uns erinnern, dass die Rippe eine Brücke ist.
Es gibt aber einen effektiveren Algorithmus, dessen Asymptomie O(n + m) ist.
P.S. Darüber hinaus werden alle Begriffe, die für den Zeilenbaum relevant sind, im Sinne des Baumes verwendet, der das Diagramm umläuft.
Für diesen Algorithmus werden wir einige Definitionen einführen:
time_in[v] ist die Zeit des Zeilenbypasses bis oben v.
bis[v] ist die minimale Zeit_in von oben, die von oben v oder von den Nachkommen von der Spitze von v kommen kann.
Wir lernen, Time_in und up zu berechnen. Wir werden ihre Bedeutungen herausfinden und gleichzeitig Brücken finden. Dafür werden wir die Zählung umgehen. Wir fangen früh an. Eine Einheit der Zeit dieses Timers wird ein Bypass zur Tiefe eines bestimmten Top sein. Wenn wir nach oben gehen, geben wir in gleicher Zeit einen Zeitwert. Jetzt legen wir den primären Wert auf das aktuelle Top. Erkennt, dass der primäre Wert die Zeit in diesem Top sein wird. Als nächstes werden wir die Rippen von der aktuellen Spitze umgehen, den Wert aktualisieren. Durch Definition, es ist sehr klar, wie es zu tun. Wir werden zwei Optionen berücksichtigen:
(1) Wird die Oberseite der Rippe noch in der Tiefe verarbeitet (aber kein Aufsatz des aktuellen Peaks), so ist die aktuelle Spitze größer als die time_in der Oberseite der Rippe, dann werden wir aktualisiert.
(2) Wenn die Oberseite der Rippen noch nicht um die Tiefen besichtigt worden ist, werden wir aus ihr herauskommen. Am Ende ihrer Verarbeitung, vergleichen Sie die aktuelle Top und oben die Spitze, die wir gerade verarbeitet. Wenn die zweite kleiner ist, werden wir den Wert im aktuellen Top aktualisieren.
Dann wird es offensichtlich, wenn die Rippe eine Brücke ist:
Lassen Sie v-u die Stromrippe sein. Dann ist v-u die Brücke, wenn up[u] tar time_in[v] (Prüfung in Absatz 2). Beweisen wir, dass es wahr ist. Je weniger time_in, desto näher die Spitze der Wurzel des Baumbypasses. Folglich werden alle Nachkommen eines bestimmten Gipfels mehr Zeit haben als dieses Gipfel. Wenn also up[u] strenger ist als time_in[v], können wir nicht aus dem Rücken, wo die Wurzel ist, v, steigen über der Oberseite v, daher, von der Oberseite, die höher ist als v, können Nachkommen v ohne Verwendung der Rippe v-u nicht erreichen. Dies bedeutet, dass ohne die v-u-Rippe die Anzahl der Verbindungen in der Reihe zunimmt, also v-u tatsächlich eine Brücke ist.

VERFAHREN
Der Verbindungspunkt ist ein solcher Peak in der Reihe, bei dem die Entnahme (also das Entfernen aller zu diesem Peak gehörenden Rippen) die Anzahl der Verbindungen in der Reihe erhöht.

Beispiel 1

Symbole sind durch die Gelenkpunkte gekennzeichnet, verschiedene Farben sind unterschiedliche Kommunikationskomponenten, die nach dem Entfernen der Gelenkpunkte gebildet werden.
Die Verbindungspunkte werden in einer Box ähnlich den Brücken gesucht. Es ist nur erforderlich, die Bedingung zu definieren, wenn der Peak der Kontaktpunkt ist.
Sehen wir die Rippe v-u. Dann ist v der Verbindungspunkt, wenn die folgende Bedingung erfüllt ist: up[u] essay= time_in[v] und, wenn v die Wurzel ist, v hat ein einzelnes Kind(en) mit dem gleichen Beweis wie die Brücken. Aber hier vergleichen wir die nicht-spicious, denn mit Gleichheit bis[u] und time_in[v] gibt es eine Rippe eines Trägers, in dem die Wurzel v ist, was zu v führt, aber sie wird auch beim Entfernen der Oberseite des v entfernt (die nicht auftreten, wenn wir die Rippen entfernt, so dass der Vergleich in den Brücken war streng). Ist v jedoch die Wurzel und hat ein Kind, wird die Kollusionskomponente nicht erhöht, so dass auch die Überprüfung erforderlich ist.

Problem


Finde alle Brücken und Gelenkpunkte im Diagramm ( die Scheitelpunktnummern sind schwarz, die Kanten sind rot). Geben Sie die Antwort in aufsteigender Reihenfolge an.
Sie müssen den Code so ergänzen, dass das Programm die Brückennummern in der ersten Zeile und die Gelenkpunktnummern in der zweiten Zeile anzeigt.

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <iostream>
#include <vector>
using namespace std;
int main()
{
 
for(int i = 0; i < arr1.size(); i++)
cout << arr1[i] << " ";
cout << endl;
for(int i = 0; i < arr2.size(); i++)
cout << arr2[i] << " ";
return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!