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 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 &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include &lt;iostream&gt;
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", &amp;u, &amp;v), u||v){

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

        for(int i = 0; i &lt; 1000; i++)
            for(int j=0; j&lt;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", &amp;u, &amp;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 &lt;= n; k++)
        for(int i = 1; i &lt;= n; i++)
        for(int j = 1; j &lt;= n; j++)
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);

        double s = 0.0;

        for(int i = 1; i &lt;= n; i++)
        for(int j=1; j&lt;=n; j++)
        s += graph[i][j];
        //cout&lt;&lt;s&lt;&lt;endl;
        s /= (double)n*(n-1);
        //cout&lt;&lt;s&lt;&lt;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 &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include &lt;iostream&gt;

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", &amp;u, &amp;v), u||v){
        for(int i = 1; i &lt;= MAX_SIZE; i++) {
            for(int j = 1; j &lt;= 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", &amp;u, &amp;v), u||v);

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

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