#include <stdio.h>
#define MAX 20

void input(int [][MAX],int,int);
void convert_to_triplet(int [][MAX],int,int,int [][3]);
void display(int [][3]);
void transpose(int [][3],int [][3]);
void sort(int [][3]);
void multiply_sparse(int [][3],int [][3],int [][3]);


int main()
{
    int r1,c1,r2,c2;

    int matrix1[MAX][MAX];
    int matrix2[MAX][MAX];
    int sparse1[MAX*MAX+1][3];
    int sparse2[MAX*MAX+1][3];
    int result[MAX*MAX+1][3];


    printf("Enter no. of rows and column in first matrix:");
    scanf("%d %d",&r1,&c1);
    do{
                printf("Enter no. of rows and column in second matrix:");
                scanf("%d %d",&r2,&c2);

        }while(r2!=c1);



    printf("Enter first matrix:\n");
    input(matrix1,r1,c1);

    printf("Enter second matrix:\n");
    input(matrix2,r2,c2);

    convert_to_triplet(matrix1,r1,c1,sparse1);
    convert_to_triplet(matrix2,r2,c2,sparse2);

    printf("Sparse representation of first matrix:\n");
    display(sparse1);

    printf("Sparse representation of second matrix:\n\n\n");
    display(sparse2);

    multiply_sparse(sparse1,sparse2,result);
    printf("Resultant matrix is:\n");
    display(result);


    return 0;
}

void multiply_sparse(int a[][3],int b[][3],int cf[][3]){
    int i,j,k=1,l=0,n=0;
    int bt[MAX*MAX+1][3];
    int c[MAX*MAX+1][3];

    c[0][0]=a[0][0];
    c[0][1]=b[0][1];

     transpose(b,bt);
     for(i=1;i<=a[0][2];i++){
         for(j=1;j<=bt[0][2];j++){
             if(a[i][1]==bt[j][1]){
                 c[k][0]=a[i][0];
                 c[k][1]=bt[j][0];
                 c[k][2]=a[i][2]*bt[j][2];
                 k++;
             }
         }
     }
  c[0][2]=k-1;
   for(i=1;i<=k-1;i++){
       for(j=i+1;j<=k-1;j++){
           if(c[i][0]==c[j][0]&&c[i][1]==c[j][1]){
               c[i][2]+=c[j][2];
               c[j][0]=-1;
            }
       }
   }
   for(i=0;i<=k-1;i++){
       if(c[i][0]!=-1){
           cf[l][0]=c[i][0];
           cf[l][1]=c[i][1];
           cf[l][2]=c[i][2];
           l++;
       }
   }
   cf[0][2]=l-1;
}

void input(int a[MAX][MAX],int r,int c){
    int i,j;
    for(i=0;i<r;i++){
        for(j=0;j<c;j++){
            printf("Enter matrix[%d][%d]:",i,j);
            scanf("%d",&a[i][j]);
        }
    }
}

void convert_to_triplet(int a[][MAX],int r,int c,int  sparse[][3]){
    int i,j,k=1;

    sparse[0][0]=r;
    sparse[0][1]=c;

    for(i=0;i<r;i++){
        for(j=0;j<c;j++){
            if(a[i][j]){
                sparse[k][0]=i;
                sparse[k][1]=j;
                sparse[k][2]=a[i][j];
                k++;
            }
        }
    }

    sparse[0][2]=k-1;
}

void display(int sparse[][3]){
    int i;
    for(i=0;i<=sparse[0][2];i++){
        printf("%d\t%d\t%d\n",sparse[i][0],sparse[i][1],sparse[i][2]);
    }
}

void transpose(int b[][3],int bt[][3]){
    int i;
    for(i=0;i<=b[0][2];i++){
        bt[i][0]=b[i][1];
        bt[i][1]=b[i][0];
        bt[i][2]=b[i][2];
    }
    sort(bt);
}

void sort(int a[][3]){
    int i,j,n,temp;
    n=a[0][2];
    for(i=1;i<n;i++){
        for(j=1;j<n-i;j++){
            if(a[j][0]>a[j+1][0]||(a[j][0]==a[j+1][0]&&a[j][1]>a[j+1][1])){

                temp=a[j][0];
                a[j][0]=a[j+1][0];
                a[j+1][0]=temp;

                temp=a[j][1];
                a[j][1]=a[j+1][1];
                a[j+1][1]=temp;

                temp=a[j][2];
                a[j][2]=a[j+1][2];
                a[j+1][2]=temp;
            }
        }
    }
}