#include <iostream>
#include <vector>
#include <queue>
#include <omp.h>
using namespace std;

class Graph
{
private:
    int V;
    vector<vector<int>> adjancentNodes;

public:
    Graph(int V)
    {
        this->V = V;
        adjancentNodes.resize(V);
    }

    void addEdge(int source, int destination)
    {
        adjancentNodes[source].push_back(destination);
        adjancentNodes[destination].push_back(source);
    }

    void bfs(int start)
    {
        vector<bool> visited(V, false);
        queue<int> currentLevel;
        visited[start] = true;
        currentLevel.push(start);

        while (!currentLevel.empty())
        {
            int levelSize = currentLevel.size();
            vector<int> nextLevel;

            #pragma omp parallel for
            for (int i = 0; i < levelSize; i++)
            {
                int node;
                // Critical section to dequeue
                #pragma omp critical
                {
                    if (!currentLevel.empty())
                    {
                        node = currentLevel.front();
                        currentLevel.pop();
                        cout << node << " ";
                    }
                }

                // Explore neighbors
                for (int neighbor : adjancentNodes[node])
                {
                    #pragma omp critical
                    {
                        if (!visited[neighbor])
                        {
                            visited[neighbor] = true;
                            nextLevel.push_back(neighbor);
                        }
                    }
                }
            }

            // Push all nextLevel nodes into queue
            for (int node : nextLevel)
                currentLevel.push(node);
        }
        cout << endl;
    }

     void dfs(int node, vector<bool> &visited)
    {
        visited[node] = true;
        cout << node << " ";

        for (int neighbor : adjancentNodes[node])
        {
            bool doVisit = false;
            #pragma omp critical
            {
                if (!visited[neighbor])
                {
                    visited[neighbor] = true;
                    doVisit = true;
                }
            }

            if (doVisit)
            {
                #pragma omp task
                dfs(neighbor, visited);
            }
        }
    }

    void startDFS(int start)
    {
        vector<bool> visited(V, false);

        #pragma omp parallel
        {
            #pragma omp single
            {
                dfs(start, visited);
            }
        }
        cout << endl;
    }
};
int main()
{
    int numNodes = 6;
    Graph graph(numNodes);

    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 4);
    graph.addEdge(3, 5);
    graph.addEdge(4, 5);

    cout << "Parallel BFS starting from node 0: ";
    graph.bfs(0);

    cout << "Parallel DFS starting from node 0: ";
    graph.startDFS(0);

    return 0;
}
