Aiuto per Connessioni di rete (connessioni)

Aiuto
1

Ciao a tutti, ho bisogno di aiuto per risolvere il problema Connessioni di rete.

Sto provando ad implementare per la prima volta l’algoritmo depht-first search, in modo da capire se il computer X è già connesso al computer Y, per poi decrescere il numero di zone se invece non lo è. Ho provato ad ottimizzare il più possibile il programma (creando la funzione inversa dell’algoritmo al posto di creare un loop che iterasse N volte, cercando di usare un unico contatore per il numero di zone che decresca anziché crearne uno nuovo che cresca ogni volta) perché ho dei problemi di TLE per gli ultimi 2 testcase, ma il vero problema è che la maggior parte dei testcase dà direttamente il risultato sbagliato e non riesco a capirne il perché (ad esempio il primo input dal testo l’output è corretto, mentre il secondo no). Qualcuno potrebbe darmi una mano, per favore?

Ecco il mio codice:

using namespace std;

int zone{};

void inizia(int N)
{
    zone = N;
}

vector<int> adj[200000];

bool visited[200000];

void processGraph(int s)
{
    if (visited[s])
        {
            return;
        }

    visited[s] = true;

    for (auto u : adj[s])
    {
        processGraph(u);
    }
}

void restoreGraph(int s)
{
    if (!visited[s])
    {
        return;
    }

    visited[s] = false;

    for (auto u : adj[s])
    {
        restoreGraph(u);
    }
}

int collega(int X, int Y)
{
    processGraph(X);

    if (visited[Y])
        return zone;

    restoreGraph(X);

    adj[X].push_back(Y);
    adj[Y].push_back(X);

    --zone;

    return zone;
}

(perdonate la mancanza di eleganza nell’inizializzare gli array, ma sono autodidatta e ho cominciato da 2 mesi, quindi sono nella fase in cui cerco di crearmi meno problemi possibile in primis XD)

Grazie mille in anticipo!

2

Ciao.
Ti segnalo che il tuo algoritmo di rompe perché hai la condizione if (visited[Y]) return zone;. Questo fa si che in quel caso non venga chiamata la funzione restoreGraph(X); e quindi alla successiva chiamata, l’array visited non è tutto uguale a false.

Detto ciò, la complessità del tuo programma è quadratica per il seguente motivo:
Prendiamo il caso pessimo con N = Q = 200000. Se le prime Q / 2 query sono collega(0, i) per i = 1, 2, ..., N / 2 e le altre Q / 2 sono collega(0, 1), allora per Q / 2 volte farai una DFS sulla componente di 0 che è grande N / 2 nodi. Ciascuna di queste seconde Q / 2 query visita N / 2 nodi, quindi la complessità che impiega la tua soluzione solo per la seconda metà delle query può essere \mathcal{O}(QN/4) = \mathcal{O}(QN).

1 Mi Piace
3

Per scrivere una soluzione più efficiente serve una struttura dati molto utile nella programmazione competitiva che fa esattamente questo:
spoiler: Disjoint Set Union (DSU)

1 Mi Piace
4

Grazie davvero! Ho sistemato il codice e ora ottengo 100/100 grazie allo spoiler (non avevo la più pallida idea che esistesse una cosa del genere!)
Un’ultima domanda: riguardo all’ “originalità delle soluzioni” per le olimpiadi… Secondo quali criteri un codice è originale? Per risolvere questo problema ho copiato le funzioni dal sito che hai mandato e poi le ho modificate un po’ per inglobarle nel problema… Non mi fanno storie dal fatto che il metodo originale l’ho imparato da lì, vero?
Grazie ancora!

1 Mi Piace
5

Diciamo che in questo caso è difficile scrivere codice con così tanta originalità, non ci sono molti modi diversi di scrivere una DSU. L’idea è che uno dovrebbe capire come funziona qualcosa e implementarlo da sé. Su un problema del genere è difficile dire che due soluzioni sono troppo simili… se due soluzioni sono esattamente identiche al byte però è evidente che sono la stessa.

Su problemi più complessi è abbastanza chiaro se due soluzioni sono una copiata dall’altra.

L’importante è non copiare e mandare ciecamente le soluzioni degli altri. Comunque nel farsi spiegare come si risolve un problema per poi scriverlo da sé non c’è niente di male.

1 Mi Piace
6

Allora dovrei essere a posto! Grazie mille!