Graf dirigit amb llistes d'adjacència. Quants vèrtexs diferents es poden visitar des de cada vèrtex X46552


Statement
 

pdf   zip   main.cc

html

Donada la classe graf que permet gestionar grafs dirigits i no etiquetats amb n vèrtexs (els vèrtexs són enters dins l’interval [0, n−1]), cal implementar el mètode

vector<nat> quants_vertexs_es_visiten() const; // Pre: Cert // Post: Retorna quants vèrtexs diferents es poden visitar (hi ha un camí) // des de cada vèrtex del graf, incloent a ell mateix.

Les arestes es guarden en llistes d’adjacència: un vector de n elements que conté vectors amb els successors de cadascun dels n vèrtexs. Un dels jocs de prova públics és aquest graf que conté 5 vèrtexs (mira el PDF de l’enunciat):

les seves arestes estarien guardades en un vector amb 5 llistes d’adjacència, els successors de cadascun dels 5 vèrtexs:

  0 [2, 1]
  1 [3]
  2 [1, 4, 3]
  3 []
  4 [0]

el qual donaria com a resultat el vector 5 2 5 1 5, indicant que hi ha 5 vèrtexs diferents que es poden visitar des del vèrtex 0 (tots els vèrtexs), hi ha 2 des del vèrtex 1 (el 1 i el 3), hi ha 5 des del vèrtex 2 (tots), hi ha 1 des del vèrtex 3 (només el 3) i hi ha 5 des del vèrtex 4 (tots).

Cal enviar a jutge.org la següent especificació de la classe graf i la implementació del mètode dins del mateix fitxer (la resta de mètodes públics ja estan implementats). Indica dins d’un comentari a la capçalera del mètode el seu cost en funció del nombre de vèrtexs n i el nombre d’arestes m del graf.

#include <vector> using namespace std; typedef unsigned int nat; class graf { // Graf dirigit i no etiquetat. // Les arestes es guarden en llistes d’adjacència (vector amb els successors). public: // Constructora per defecte. Crea un graf buit. graf(); // Destructora ~graf(); // Llegeix les dades del graf del canal d’entrada void llegeix(); vector<nat> quants_vertexs_es_visiten() const; // Pre: Cert // Post: Retorna quants vèrtexs diferents es poden visitar (hi ha un camí) // des de cada vèrtex del graf, incloent a ell mateix. private: nat n; // Nombre de vèrtexs nat m; // Nombre d’arestes vector<vector<nat> > a; // Vectors amb els successors de cada vèrtex // Aquí va l’especificació dels mètodes privats addicionals }; // Aquí va la implementació del mètode públic quants_vertexs_es_visiten i privats addicionals



Degut a que jutge.org només permet l’enviament d’un fitxer amb la solució del problema, en el mateix fitxer hi ha d’haver l’especificació de la classe i la implementació del mètode quants_vertexs_es_visiten (el que normalment estarien separats en els fitxers .hpp i .cpp).

Per testejar la classe disposes d’un programa principal que llegeix un graf i després crida el mètode quants_vertexs_es_visiten.

Entrada

L’entrada conté un graf: el nombre de vèrtexs, el nombre d’arestes i una llista d’arestes. Cada aresta s’indica pels dos vèrtexs que relaciona.

Sortida

Escriu una línia amb el nombre de vèrtexs diferents que es poden visitar des de cada vèrtex del graf separats per espais.

Observació

Només cal enviar la classe requerida i la implementació del mètode quants_vertexs_es_visiten. Pots ampliar la classe amb mètodes privats. Segueix estrictament la definició de la classe de l’enunciat.

Indica dins d’un comentari a la capçalera del mètode el seu cost en funció del nombre de vèrtexs n i el nombre d’arestes m del graf.

Public test cases

  • Input

    1
0

    Output

    1

  • Input

    2
0

    Output

    1 1

  • Input

    2
1
0 1

    Output

    2 1

  • Input

    2
2
0 1
1 0

    Output

    2 2

  • Input

    3
4
0 2
0 1
1 2
2 0

    Output

    3 3 3

  • Input

    5
7
4 0
0 2
0 1
2 1
2 4
2 3
1 3

    Output

    5 2 5 1 5

  • Input

    6
9
1 5
1 0
3 1
4 0
0 5
5 1
2 3
0 1
5 0

    Output

    3 3 5 4 4 3
    • Information
    Author
    Jordi Esteve
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++