Optimizing graph analysis

Question

I've implemented the Floyd Warshall algorithm in this problem. However, as this is my first time in handling with adjacency list, I was not able to make it memory efficient.

I used a 1000*1000 and another list of 1000 size but I have seen solutions of people getting accepted with 100*100 size. How can I make my graph array size less, or perhaps what is the best possible way to accept input in the adjacency list in graph?

P.S.: I tried using vector and map/pairs STL, but since I am not good in STL, I will be more than happy if a non STL solution is presented.

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 1e9
int graph[1000][1000], m[1001], n;  //this is the array which I want to decrease
int main(){
    int u, v, flag=0, testCase = 1;
    while(scanf("%d%d", &u, &v), u||v){

        n = 0;
        memset(m, 0, sizeof(m));

        for(int i = 0; i < 1000; i++)
            for(int j=0; j<1000; j++)
            graph[i][j] = INF;

        if(!m[u])
        m[u] = ++n;

        if(!m[v])
        m[v] = ++n;

        graph[m[u]][m[v]] = 1;
        graph[m[u]][m[u]] = 0;
        graph[m[v]][m[v]] = 0;

        while(scanf("%d%d", &u, &v), u||v){
            if(!m[u])
            m[u] = ++n;

            if(!m[v])
            m[v] = ++n;

            graph[m[u]][m[v]] = 1;
            graph[m[u]][m[u]] = 0;
            graph[m[v]][m[v]] = 0;
        }

        for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);

        double s = 0.0;

        for(int i = 1; i <= n; i++)
        for(int j=1; j<=n; j++)
        s += graph[i][j];
        //cout<<s<<endl;
        s /= (double)n*(n-1);
        //cout<<s<<endl;
        printf("Case %d: average length between pages = %.3lf clicks\n",testCase++,s);
    }
    return 0;
    } 

Running here

Answer 1

Problem statement linked above says 'Page numbers will always be in the range 1 to 100', I don't understand why you need to keep size = 1000, size = 101 should work just fine. Correct me if I am missing something here.

I modified your code here

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

#define INF 1e9
#define MAX_SIZE 100

int graph[MAX_SIZE + 1][MAX_SIZE + 1], n, mapping[MAX_SIZE + 1];
int main() {
    int u, v, flag=0, testCase = 1;
    while(scanf("%d%d", &u, &v), u||v){
        for(int i = 1; i <= MAX_SIZE; i++) {
            for(int j = 1; j <= MAX_SIZE; j++) {
                graph[i][j] = INF;
            }
            graph[i][i] = 0;
        }
        int n = 0;
        memset (mapping, 0, sizeof(mapping));
        do {
            if (!mapping[u])
                mapping[u] = ++n;
            if (!mapping[v])
                mapping[v] = ++n;
            graph[mapping[u]][mapping[v]] = 1;
        } while(scanf("%d%d", &u, &v), u||v);

        for(int k = 1; k <= n; k++)
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);

        double s = 0.0;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                s += graph[i][j];
        //cout<<s<<endl;
        s /= (double)n*(n-1);
        //cout<<s<<endl;
        printf("Case %d: average length between pages = %.3lf clicks\n",testCase++,s);
    }
    return 0;
}

Answer 2

Use the standard library

I tried using vector and map/pairs STL, but since I am not good in STL, I will be more than happy if a non STL solution is presented.

You should rather ask for a detailed standard library based solution ("STL" refers to "standard template library" on which some parts of the standard library are based but which is not the standard library). Honestly, it may take some time in the beginning, but it is totally worth it. Currently, appart from std::min, you are not using anything that is C++-specific.

using namespace std; is evil

using namespace std; is probably the biggest single mistake that you will see in many tutorials all around the internet. It is not something you should do since it may create name problems and very unexpected errors from time to time. Just put std:: in front of every component you import from the standard library.

Order your headers

That's not that important, but you will probably find it easier to check whether you already included some header if you order them in alphabetical ordering:

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>

Get rid of dead code

You should try to avoid keeping code that you commented out. You will probably end up deleting it at some point anyway since you won't remember what you wanted to do with it or why it worked/didn't work.

You don't need to return 0; at the end of main

When you program reaches the end of the funciton main, if it did not find any return statement, it will automagically return 0;. Note that this is only true for main, but in your case, that means that you can get rid of this last line.