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;
}
}
}
Input
3 1 2 3
1 3 2
2 2 3
4 -1
0
3 1 2 3
5 -2 11
Output
2 1 4
1 5
3 1 2 4
3 4 -2
3 1 2 4
Demonstration
UVA Online Judge solution - 10895-Matrix Transpose - UVA Online Judge solution in C,C++,java