Matrius esparses (2): transposició Y91345

Tal com vam veure al problema Matrius esparses (1): conversió, una matriu esparsa només emmagatzema els elements no nuls. Els tipus usats (definits a matrius.hh) són els mateixos:

struct Casella {
    int pos;    // índex de columna
    int valor;  // valor de l'element
};

struct MatriuEsparsa {
    int ncols;                   // nombre de columnes
    vector<list<Casella>> files; // files de la matriu esparsa
};

La transposada d’una matriu $n \times m$ és la matriu $m \times n$ que s’obté intercanviant files i columnes: l’element a la posició $(i, j)$ de l’original passa a la posició $(j, i)$ de la transposada.

Fes la funció següent:

/**
 * @brief Calcula la transposada d'una MatriuEsparsa.
 *
 * @param S MatriuEsparsa de S.files.size() files i S.ncols columnes.
 *
 * @pre S és una MatriuEsparsa vàlida. Les posicions de les caselles van de 0 a S.ncols-1.
 * @post Retorna una nova MatriuEsparsa T amb T.ncols == S.files.size() i
 *       T.files.size() == S.ncols, on T.files[j] conté les caselles
 *       {i, S.files[i][j].valor} de S, ordenades per columna ascendentment.
 */
MatriuEsparsa matriu_esparsa_transposa(const MatriuEsparsa& S);

Observació

Els fitxers públics (icona del gatet) contenen:

Cal enviar únicament la implementació de la funció matriu_esparsa_transposa, incloent-hi l’include de matrius.hh. No cal enviar el main.

Entrada

La primera línia conté dos enters $n$ i $m$ ($0 \leq n, m \leq 1000$), el nombre de files i columnes de la matriu esparsa d’entrada. A continuació hi ha $n$ línies, cadascuna amb les caselles no nul·les de la fila com a parelles (col,val) separades per espais, seguides d’un punt .. Les files sense elements no nuls es representen com ..

Sortida

La matriu esparsa transposada en el mateix format que l’entrada: la primera línia conté les dimensions $m \times n$ de la transposada, seguida de $m$ línies amb les caselles no nul·les de cada fila, seguides d’un punt ..