ISI2020-PCB-CS: 2

Question

An $n \times n$ binary matrix $M$ is called a NICE matrix, if each row of $M$ has exactly one non-zero element and each column also has exactly one non-zero element.

1. Suggest a method of storing a NICE matrix in an $O(n)$ size array.
2. Design an $O(n)$ time algorithm (in pseudocode) for computing $R=P Q$, where $P$ and $Q$ are both NICE matrices each stored in an array of size $O(n)$ as in (i).