Police 2 35/100

Aiuto
1

Ciato a tutti stavo cercando di risolvere police 2, ma non riesco a prendere 100/100 per 5 subtasks.
Questo è il codice:

#include <bits/stdc++.h>
using namespace std;

int v[100000], dist[100000], N, i;


void DFS(int n, int d){
    if(dist[n] != 0) return;

    if(dist[n] < d) dist[n] = d;

    DFS(v[n], d + 1);

}

int main() {
    cin >> N;

    for(; i < N; ++i) cin >> v[i];
    
    for(i = 0; i < N; ++i) DFS(i, 0);
    

    int m = dist[0];
    for(i = 1; i < N; ++i) m = max(m, dist[i]);

    cout << m;
    return 0;
}

Qualcuno ha qualche idea?

2

Con questo input del primo test case d’esempio modificato

10
1 4 6 3 7 6 8 5 9 7

il tuo codice restituisce 7 invece di 5.
questo perché la lunghezza del ciclo non viene calcolata correttamente in quanto consideri il ciclo più la distanza iniziale dal ciclo.

3

Ciao, grazie per la risposta, ho capito il problema però non so come implementarlo… :frowning: Potresti darmi una mano?

4

Seguendo l’input dato come suggerimento, con vista in profondità si fa il seguente percorso: 0, 1, 4, 7, 5, 6, 8, 9, 7.
Partendo dal nodo 0 il ciclo inizia dal nodo 7 e quindi hai percorso una distanza dist[n] = d = 3 (dist_prev) quando il ciclo si chiude hai percorso una distanza d = 8 (dist_curr) e la lunghezza del ciclo risulta:
dist_curr - dist_prev = 5.
Per trovare il ciclo di lunghezza massima utilizzando il tuo codice devi trovare nella DFS la max_dist = max{dist_curr - dist[n]} e prendi 100/100.

1 Mi Piace
5

Grazie mille, finalmente ci sono riuscito! Avevo già provato a risolverlo, il problema era che assegnavo a dist[n] = d - dist[n] (quando visto[n] == 1), ciò é sbagliato perché bisogna assegnare dist[n] = d ogni volta che entra in un nuovo grafo ancora non visitato.