Algorithm


problem Link ; https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1836 

A matrix is a rectangular array of elements, most commonly numbers. A matrix with m rows and n
columns is said to be an m-by-n matrix. For example,
A =



1 3 2
0 4 −1
0 0 0
5 −2 11



is a 4-by-3 matrix of integers.
The individual elements of a matrix are usually given lowercase symbols and are distinguished by
subscripts. The ith row and jth column of matrix A is usually referred to as aij . For example, a23 = −1.
Matrix subscripts are 1-based.
The transpose of a matrix M , denoted M T , is formed by interchanging the rows and columns of M .
That is, the ij-th element of M T is the ji-th element of M . For example, the transpose of matrix A
above is:
AT =

 1 0 0 5
3 4 0 −2
2 −1 0 11


A matrix is said to be sparse if there are relatively few non-zero elements. As a m-by-n matrix has
mn number of elements, storing all elements of a large sparse matrix may be inefficient as there would
be many zeroes. There are a number of ways to represent sparse matrices, but essentially they are all
the same: store only the non-zero elements of the matrix along with their row and column.
You are to write a program to output the transpose of a sparse matrix of integers.
Input
You are given several sparse matrix in a row, each of them described as follows. The rst line of the
input corresponds to the dimension of the matrix, m and n (which are the number of rows and columns,
respectively, of the matrix). You are then given m sets of numbers, which represent the rows of the
matrix. Each set consists of two lines which represents a row of the matrix. The rst line of a set starts
with the number r, which is the number of non-zero elements in that row, followed by r numbers which
correspond to the column indices of the non-zero elements in that row, in ascending order; the second
line has r integers which are the matrix elements of that row. For example, matrix A above would have
the following representation:
4 3
3 1 2 3
1 3 2
2 2 3
4 -1
0
3 1 2 3
5 -2 11
Note that for a row with all zero elements, the corresponding set would just be one number, `0', in
the rst line, followed by a blank line.
You may assume:
• the dimension of the sparse matrix would not exceed 10000-by-10000,
• the number of non-zero element would be no more than 1000,
• each element of the matrix would be in the range of -10000 to 10000, and
• each line has no more than 79 characters.
Output
For each input case, the transpose of the given matrix in the same representation.
Sample Input
4 3
3 1 2 3
1 3 2
2 2 3
4 -1
0
3 1 2 3
5 -2 11
Sample Output
3 4
2 1 4
1 5
3 1 2 4
3 4 -2
3 1 2 4
2 -1 11

Code Examples

#1 Code Example with C Programming

Code - C Programming

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

int main() {
    int m,n;
    int s,v;
    while(scanf("%d %d",&m,&n) != EOF){
        vector < vector<pair<int,int>>> transpose(n,vector < pair<int,int>>());
        for(int i=0;i < m;i++){
            cin >> s;
            vector<int> pos;
            for(int j=0;j < s;j++){
                cin >> v;
                pos.push_back(v-1);
            }
            for(int j=0;j < s;j++){
                cin >> v;
                transpose[pos[j]].push_back({v,i+1});
            }
        }
        printf("%d %d\n",n,m);
        for(int i=0;i < n;i++){
            cout << transpose[i].size();
            for(auto& p : transpose[i]) cout << " " << p.second;
            cout << endl;
            for(auto& p : transpose[i])
                cout << p.first << (&p == &transpose[i].back() ? "" : " ");
            cout << endl;
        }
    }
}

Copy The Code & Try With Live Editor

Input

x
+
cmd
4 3
3 1 2 3
1 3 2
2 2 3
4 -1
0
3 1 2 3
5 -2 11

Output

x
+
cmd
3 4
2 1 4
1 5
3 1 2 4
3 4 -2
3 1 2 4
Advertisements

Demonstration


UVA Online Judge solution - 10895-Matrix Transpose - UVA Online Judge solution in C,C++,java

Previous
UVA Online Judge solution - 10892-LCM Cardinality - UVA Online Judge solution in C,C++,java
Next
UVA Online Judge solution - 10901-Ferry Loading III - UVA Online Judge solution in C,C++,java

Category - UVA Online Judge   Maniruzzaman Akash   4 months ago   173   0