[C++] Rappresentare grafo letto da input

[AyFrank]

Salve a tutti, vengo subito al problema, può sembrare banale ma ci sto sbattendo la testa da un paio di giorni, sapendo che devo calcolare un minimo albero ricoprente (e quindi la mia rappresentazione deve adattarsi a questo problema - ma non è questo l'argomento del topic), ho in input una serie di casi test del tipo:

N (un intero positivo che rappresenta gli archi del grafo)
X - Y distanza
Y - Z distanza
X - Z distanza

non mi viene in mente niente per rappresentare in maniera efficiente questo tipo di input, anche perché non so di preciso quanti vertici potrò avere, essendo il grafo connesso con N archi posso teoricamente avere da N+1 a N*2 vertici (correggetemi se dico qualche cazzata). Il problema che mi affligge di più è: preso un vertice X dall'input controllare se è già presente nella mia rappresentazione, contando che N può arrivare fino a 1.000.000, può rilevarsi molto costoso se non implementato efficientemente...

Mi affido a voi per qualche suggerimento...

[Roby.zip]

Ciao,
per questo tipo di problemi si usano le hashmap, che permettono in modo quasi immediato di controllare che una data chiave sia o meno presente nella collezione.

[AyFrank]

Ciao, effettivamente avevo pensato ad una soluzione del genere, ma poi sul concreto non riuscivo ad astrarre il concetto di tabella hash per rappresentare un grafo. Così facendo non si perderebbe parte del potere rappresentativo? Risolverei il problema dell'insert/search ma riuscirei comunque a scrivere degli algoritmi efficienti sui grafi rappresentati mediante mappa hash? Perché per quanto ne so io al momento stiamo parlando di un vettore i cui elementi puntano a liste di oggetti (magari devo approfondire l'argomento)..