4 - BDS using BFS

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;

#define MAX 1000
#define pb push_back

class Graph{
            int nodes;
            int x = 0;
            vector <int> *edges;
        public:
            Graph(int vertex){
                this->nodes = vertex;
                edges = new vector <int>[MAX];
            }
            void addEdge(int src, int to){
                edges[src].pb(to);
                edges[to].pb(src);
            }
            //General BFS implementation
            void BFS(list <int> *q, bool *visited, int *parent){
                int curr = q->front();
                q->pop_front();
                for(auto it=edges[curr].begin(); it!=edges[curr].end(); it++){
                    if(!visited[*it]){
                        parent[*it] = curr;
                        visited[*it] = true;
                        q->pb(*it);
                    }
                }
            }
            int checkIntersection(bool *sourceFlag, bool *destFlag){
                int intersect = -1;
                for(int i=0; i<nodes; i++)
                    if(sourceFlag[i] && destFlag[i]) //Dua-duanya visit titik yang sama = udah ketemu pathnya
                        return i;
                return -1;
            }
            void BDS(int from, int to){
                bool startVisited[nodes] = {0}, endVisited[nodes] = {0}; //Nyimpen node yang udh divisit
                int startParent[nodes], endParent[nodes]; //Nyimpen parent node kedua sisi
                list <int> startQueue, endQueue;
                int intersect;
                //Inisialisasi default value kedua sisi
                startQueue.pb(from);
                startVisited[from] = true;
                startParent[from] = -1;
                endQueue.pb(to);
                endVisited[to] = true;
                endParent[to] = -1;
                //Main loop
                while(!startQueue.empty() && !endQueue.empty()){
                    //BFS dari kedua sisi
                    BFS(&startQueue, startVisited, startParent);
                    BFS(&endQueue, endVisited, endParent);
                    //Cek kalo udah ketemu atau blm
                    intersect = checkIntersection(startVisited, endVisited);
                    if(intersect != -1){
                        cout << "Path found! Intersect at node " << intersect << endl;
                        printPath(startParent, endParent, from, to, intersect);
                        return;
                    }
                }
                cout << "Path not found!" << endl;
            }
            void printPath(int *startParent, int *endParent, int from, int to, int intersect){
                int *prev = startParent;
                vector <int> paths;
                for(int i=0; i<2; i++){ //Satu dari titik asal, satu dari titik akhir
                    int meetPoint = intersect;
                    while(meetPoint != -1){
                        paths.pb(meetPoint);
                        int prevNode = prev[meetPoint];
                        meetPoint = prevNode;
                    }
                    prev = endParent;
                }
                //Print Path
                for(auto i = paths.begin() + 1; i != paths.end(); i++){
                    cout << *i << (i == paths.end() - 1 ? "" : "->");
                }
            }
};

int main(){
    int edges, from, to;
    cout << "How many edges ? ";
    cin >> edges;
    Graph graph(edges);
    cout << "Enter " << edges << " edeges (from-to) separated by a space:" << endl;
    while(edges--){
        cin >> from >> to;
        graph.addEdge(from, to);
    }
    cout << "Enter source and destination node: ";
    cin >> from >> to;
    graph.BDS(from, to);
    return 0;
}