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


class Graph {

private:
	int V;
	vector<vector<int>> adj;

	void dfs_act(int node, vector<bool>& v){
		bool flag = false;		
		#pragma omp critical 
		{
			if(v[node]){
				flag = true;
			} else {
				v[node] = true;
				cout << node << "\t";
			}
		}	
		
		if(flag) return;

		for(int i = 0; i < V; i++){
			
			#pragma omp critical
			{
				if(adj[node][i]==1 && !v[i]){
					
					#pragma omp task 
					{
						dfs_act(i, v);
					}
				}

			}


		}

		#pragma omp taskwait

	}	

public:
	Graph(int v){
		adj.resize(v, vector<int>(v, 0));
		V = v;

	}

	void addEdge(int v, int u){
		adj[v][u] = 1;
		adj[u][v] = 1;
		
	}
	
	// Sequntial
	
	void bfs(int start){
		vector<bool> visited(V, false);
		queue<int> q;
		
		visited[start] = true;

		q.push(start);

		while(!q.empty()){
			
			int c = q.front();
			q.pop();
			
			cout << c << "\t";
			
			for(int i = 0; i < V; i++){
				
				if(adj[c][i] == 1 && !visited[i]){
					q.push(i);
					visited[i] = true;
				}
			
			}
		
		}

		cout << endl;
		

	}


	void dfs(int start){
		vector<bool> visited(V, false);
		
		stack<int> s;
		
		s.push(start);
	
		while(!s.empty()){

			int c = s.top();
			s.pop();
			
			visited[c] = true;
			
			cout << c << "\t";
			
			for(int i = 0; i < V; i++){
				if(adj[c][i] == 1 && !visited[i]){
					s.push(i);
				
				}
			}

		}

		cout << endl;

	}

// parallel
	void bfs_p(int start){
		vector<bool> visited(V, false);
		queue<int> q;
		
		visited[start] = true;

		q.push(start);

		while(!q.empty()){
			
			int c = q.front();
			q.pop();
			
			cout << c << "\t";
			#pragma omp parallel for	
			for(int i = 0; i < V; i++){
				
				#pragma omp critical
				{
					if(adj[c][i] == 1 && !visited[i]){
						q.push(i);
						visited[i] = true;
					}
				}
			}
		
		}

		cout << endl;
		

	}
	
	void dfs_p(int start){
		
		vector<bool> visited(V, false);
		
		int s = start;

		#pragma omp parallel
		#pragma omp single
		dfs_act(s, visited);
		cout << endl;

	}


};




int main(){

    Graph g(7);
    // Tree-like undirected graph:
    //      0
    //    / | \
    //   1  2  3
    //  / \    |
    // 4   5   6
    g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(0, 3);
    g.addEdge(1, 4); g.addEdge(1, 5); g.addEdge(3, 6);
	
	int start, end;
	
	start = omp_get_wtime();
	g.bfs(0);
	end = omp_get_wtime();

	cout << (end - start) << endl;

	start = omp_get_wtime();
	g.bfs_p(0);	

	end = omp_get_wtime();

	cout << (end - start) << endl;

	g.dfs(0);

	g.dfs_p(0);

	return 0;
}