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


vector<vector<int>> graph;
vector<vector<int>> graph_q
int V;

void randomGraph(int vertices, int edges) {
    V = vertices;
    graph.assign(V, vector<int>(V, 0));
    srand(time(0));
    int count = 0;
    while (count < edges) {
        int u = rand() % V;
        int v = rand() % V;
        if (u != v && graph[u][v] == 0) {
            graph[u][v] = 1;
            graph[v][u] = 1;
            count++;
        }
    }
    cout << "Random graph created: " << V << " nodes, " << edges << " edges\n";
}


void bfs(int node){

	int size = graph.size();	
	queue<int> q;
	vector<bool> visited(size, false);
	q.push(node);
	
	int current;

        visited[current] = true;


	while(!q.empty()){
		current = q.front(); q.pop();
		cout << current << "\t";		
//		#pragma omp parallel for(static, 10)	
		#pragma omp parelle for(dyanmic)
		for(int i = 0; i < size; i++){
			// critical cuz that(visited vector) is shared between thread
			#pragma omp critical
			{
				if(visited[i] != true && graph[current][i] == 1){
					visited[i] = true;
					q.push(i);
				}
			}
		}		
	

	}

	cout << endl;
	


}



void dfs(int node){

	queue<int> q;
	vector<bool> visited;
	
	q.push(node);
	
	while(!q.empty()){
		
		int n = q.pop();
		
		cout << n << "\t";
		
		

	}	

}


int main(){
	
	cout << "Enter Number of edges(maximum of 10000000): ";
	cin >> V;
	cout << endl;
	
	graph.assign(V, vector<int>(V));
	
	int exi = 0;
	
	int g1 = -1;
	int g2 = -1;

//	while(exi == 0){
	//	cout << "Enter node 1: " << endl;
	//	cin >> g1;
//		cout << endl;
//		cout << "Enter node 2: " << endl;
  //              cin >> g2;
    //            cout << endl;
//		graph[g1][g2] = 1;
//		graph[g2][g1] = 1;
		
//		cout << "Do you want to continue? (enter 0 to continue or 1 to exit) : " << endl;
//		cin >> exi;
//		cout << endl;	
		
//	}

	
	randomGraph(V, V);
	bfs(0);	
	
	return 0;
}