#include <stdio.h>
#include <stdlib.h>

#include "Graph.h"
#include "Queue.h"

int furthestReachable(Graph g, int src) {
    if (g == NULL) {
        return -1;
    }

    int nV = GraphNumVertices(g);
    int dist[nV];

    // Init dist array setting src to be 0
    for (int i = 0; i < nV; i++) {
        if (i == src) {
            dist[i] = 0;
        }
        else {
            dist[i] = -1;
        }
    }

    Queue q = QueueNew();
    QueueEnqueue(q, src);
    int max = src;
    while (QueueIsEmpty(q) == false) {
        int v = QueueDequeue(q);
        for(int i = 0; i < nV; i++) {
            if (GraphIsAdjacent(g, i, v) == true && dist[i] == -1) {
                dist[i] = dist[v] + 1;
                if (dist[i] >= dist[max]) {
                    max = i;
                }
                QueueEnqueue(q, i);
            }
        }
    }

    QueueFree(q);
    return max;
}