Description
Problem: Matrix Transpose of sparse Matrix
1
2
3
4
5
6
7
8
1 3 2
A = 0 4 −1
0 0 0
5 −2 11
1 0 0 5
A' = 3 4 0 −2
2 −1 0 11
Sample Input
You are given several sparse matrix in a row, each of them described as follows. The first 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 first 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:
1
2
3
4
5
6
7
8
9
10
4 3
3 1 2 3
1 3 2
2 2 3
4 -1
0
3 1 2 3
5 -2 11
Sample Output
For each input case, the transpose of the given matrix in the same representation.
1
2
3
4
5
6
7
8
3 4
2 1 4
1 5
3 1 2 4
3 4 -2
3 1 2 4
2 -1 11
Ideas
Store each indices as (row, col, val) then for transpose we just need to flipp it with (col, row, val)
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
int main()
{
int m, n;
while (scanf("%d %d", &m, &n) != EOF)
{
int t = m;
vector<vector<pair<int, int>>> mat(m + 1, vector<pair<int, int>>()), matT(n + 1, vector<pair<int, int>>());
for (int j = 1; j <= m; j++)
{
int a;
scanf("%d", &a);
int places[a];
vector<pair<int, int>> cord;
for (int i = 0; i < a; i++)
{
scanf("%d ", &places[i]);
}
for (int i = 0; i < a; i++)
{
int b;
scanf("%d", &b);
mat[j].push_back({places[i], b});
}
}
for (int i = 1; i <= m; i++)
{
for (int j = 0; j < mat[i].size(); j++)
{
int p = mat[i][j].first;
int r = mat[i][j].second;
int z = i;
matT[p].push_back({z, r});
}
}
cout << n << " " << m << endl;
for (int i = 1; i <= n; i++)
{
cout << matT[i].size();
for (int j = 0; j < matT[i].size(); j++)
{
cout << " " << matT[i][j].first;
}
cout << endl;
for (int j = 0; j < matT[i].size(); j++)
{
if (i == matT[i].size() - 1)
cout << matT[i][j].second;
else
cout << matT[i][j].second << " ";
}
cout << endl;
}
}
return 0;
}