Suche nach einem Zyklus in einer Permutation mit maximaler Summe

Python Hard loops

Aufgabe «Suche nach einem Zyklus in einer Permutation mit maximaler Summe»

Gegeben ist eine Permutation der Zahlen von 1 bis N. Betrachten Sie einen gerichteten Graphen, in dem jeder Knoten i eine Kante zu a[i] hat. Finden Sie einen Zyklus in diesem Graphen, dessen Summe der Elemente maximal ist. Falls es mehrere solcher Zyklen gibt, geben Sie einen beliebigen aus. Es ist garantiert, dass N ≥ 2. Ein Zyklus ist definiert als eine Folge von verschiedenen Knoten, bei der jeder nächste Knoten nach der Regel erhalten wird: nächster = a[aktueller], und der letzte Knoten kehrt über eine Kante zum ersten zurück.

Eingabeformat

Die erste Zeile enthält eine ganze Zahl N (2 ≤ N ≤ 10^5). Die zweite Zeile enthält N ganze Zahlen a[1], a[2], ..., a[N] — eine Permutation der Zahlen von 1 bis N.

Ausgabeformat

Geben Sie zwei Zahlen aus: die Länge des Zyklus und die Summe der Elemente des Zyklus. Geben Sie dann in der nächsten Zeile die Elemente des Zyklus in der Reihenfolge des Durchlaufs aus, beginnend mit einem beliebigen Element.

Beispiele

Beispiel 1

EINGABE

5
2 3 1 5 4

AUSGABE

2 9
4 5

Beispiel 2

EINGABE

7
1 2 3 4 5 6 7

AUSGABE

1 7
7

Beispiel 3

EINGABE

4
abc
cde
xyz
zab

AUSGABE

Invalid input

Beispiel 4

EINGABE

4
2 1 4 3

AUSGABE

2 7
3 4

Beispiel 5

EINGABE

3
1 0 2

AUSGABE

1 1
1

main.py