Optimizing graph analysis

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 10001000 and another list of 1000 size but I have seen solutions of people getting accepted with 100100 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 
#include 
#include 
#include 
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

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 
#include 
#include 
#include 

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;
}

StackExchange Code Review Q#54015, answer score: 6