Recherche d’un cycle dans une permutation avec somme maximale

Python Hard loops

Tâche «Recherche d’un cycle dans une permutation avec somme maximale»

Soit une permutation des nombres de 1 à N. Considérons un graphe orienté où chaque sommet i a une arête vers a[i]. Trouvez un cycle dans ce graphe dont la somme des éléments est maximale. S’il existe plusieurs cycles de ce type, affichez n’importe lequel. Il est garanti que N ≥ 2. Un cycle est défini comme une séquence de sommets distincts, où chaque sommet suivant est obtenu par la règle : suivant = a[courant], et le dernier sommet revient au premier par une arête.

Format d\ entrée

La première ligne contient un entier N (2 ≤ N ≤ 10^5). La deuxième ligne contient N entiers a[1], a[2], ..., a[N] — une permutation des nombres de 1 à N.

Format de sortie

Affichez deux nombres : la longueur du cycle et la somme des éléments du cycle. Ensuite, sur la ligne suivante, affichez les éléments du cycle dans l’ordre du parcours, en commençant par n’importe quel élément.

Exemples

Exemple 1

ENTRÉE

5
2 3 1 5 4

SORTIE

2 9
4 5

Exemple 2

ENTRÉE

7
1 2 3 4 5 6 7

SORTIE

1 7
7

Exemple 3

ENTRÉE

4
abc
cde
xyz
zab

SORTIE

Invalid input

Exemple 4

ENTRÉE

4
2 1 4 3

SORTIE

2 7
3 4

Exemple 5

ENTRÉE

3
1 0 2

SORTIE

1 1
1

main.py