#include <iostream>
#include <vector>
#include <queue>
#include <omp.h>
using namespace std;
// Structure to represent a graph
struct Graph {
int V; // Number of vertices
vector<vector<int>> adj; // Adjacency list
};
// Breadth-First Search (BFS) Algorithm
void parallelBFS(const Graph& graph, int start) {
vector<bool> visited(graph.V, false);
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
#pragma omp parallel
{
int current;
#pragma omp critical
{
current = q.front();
q.pop();
}
#pragma omp for
for (int i = 0; i < graph.adj[current].size(); ++i) {
int neighbor = graph.adj[current][i];
if (!visited[neighbor]) {
visited[neighbor] = true;
#pragma omp critical
{
q.push(neighbor);
}
}
}
}
}
}
int main() {
Graph graph;
graph.V = 6;
graph.adj = {
{1, 2}, // Node 0 is connected to nodes 1 and 2
{0, 3, 4}, // Node 1 is connected to nodes 0, 3, and 4
{0, 5}, // Node 2 is connected to nodes 0 and 5
{1}, // Node 3 is connected to node 1
{1}, // Node 4 is connected to node 1
{2} // Node 5 is connected to node 2
};
// Perform BFS from node 0
cout << "Breadth-First Search (BFS) starting from node 0:\n";
parallelBFS(graph, 0);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxvbXAuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBTdHJ1Y3R1cmUgdG8gcmVwcmVzZW50IGEgZ3JhcGgKc3RydWN0IEdyYXBoIHsKICAgIGludCBWOyAvLyBOdW1iZXIgb2YgdmVydGljZXMKICAgIHZlY3Rvcjx2ZWN0b3I8aW50Pj4gYWRqOyAvLyBBZGphY2VuY3kgbGlzdAp9OwoKLy8gQnJlYWR0aC1GaXJzdCBTZWFyY2ggKEJGUykgQWxnb3JpdGhtCnZvaWQgcGFyYWxsZWxCRlMoY29uc3QgR3JhcGgmIGdyYXBoLCBpbnQgc3RhcnQpIHsKICAgIHZlY3Rvcjxib29sPiB2aXNpdGVkKGdyYXBoLlYsIGZhbHNlKTsKICAgIHF1ZXVlPGludD4gcTsKICAgIHEucHVzaChzdGFydCk7CiAgICB2aXNpdGVkW3N0YXJ0XSA9IHRydWU7CgogICAgd2hpbGUgKCFxLmVtcHR5KCkpIHsKICAgICAgICAjcHJhZ21hIG9tcCBwYXJhbGxlbAogICAgICAgIHsKICAgICAgICAgICAgaW50IGN1cnJlbnQ7CiAgICAgICAgICAgICNwcmFnbWEgb21wIGNyaXRpY2FsCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGN1cnJlbnQgPSBxLmZyb250KCk7CiAgICAgICAgICAgICAgICBxLnBvcCgpOwogICAgICAgICAgICB9CgogICAgICAgICAgICAjcHJhZ21hIG9tcCBmb3IKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBncmFwaC5hZGpbY3VycmVudF0uc2l6ZSgpOyArK2kpIHsKICAgICAgICAgICAgICAgIGludCBuZWlnaGJvciA9IGdyYXBoLmFkaltjdXJyZW50XVtpXTsKICAgICAgICAgICAgICAgIGlmICghdmlzaXRlZFtuZWlnaGJvcl0pIHsKICAgICAgICAgICAgICAgICAgICB2aXNpdGVkW25laWdoYm9yXSA9IHRydWU7CiAgICAgICAgICAgICAgICAgICAgI3ByYWdtYSBvbXAgY3JpdGljYWwKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIHEucHVzaChuZWlnaGJvcik7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9CgppbnQgbWFpbigpIHsKICAgIEdyYXBoIGdyYXBoOwogICAgZ3JhcGguViA9IDY7CiAgICBncmFwaC5hZGogPSB7CiAgICAgICAgezEsIDJ9LCAvLyBOb2RlIDAgaXMgY29ubmVjdGVkIHRvIG5vZGVzIDEgYW5kIDIKICAgICAgICB7MCwgMywgNH0sIC8vIE5vZGUgMSBpcyBjb25uZWN0ZWQgdG8gbm9kZXMgMCwgMywgYW5kIDQKICAgICAgICB7MCwgNX0sIC8vIE5vZGUgMiBpcyBjb25uZWN0ZWQgdG8gbm9kZXMgMCBhbmQgNQogICAgICAgIHsxfSwgLy8gTm9kZSAzIGlzIGNvbm5lY3RlZCB0byBub2RlIDEKICAgICAgICB7MX0sIC8vIE5vZGUgNCBpcyBjb25uZWN0ZWQgdG8gbm9kZSAxCiAgICAgICAgezJ9IC8vIE5vZGUgNSBpcyBjb25uZWN0ZWQgdG8gbm9kZSAyCiAgICB9OwoKICAgIC8vIFBlcmZvcm0gQkZTIGZyb20gbm9kZSAwCiAgICBjb3V0IDw8ICJCcmVhZHRoLUZpcnN0IFNlYXJjaCAoQkZTKSBzdGFydGluZyBmcm9tIG5vZGUgMDpcbiI7CiAgICBwYXJhbGxlbEJGUyhncmFwaCwgMCk7CgogICAgcmV0dXJuIDA7Cn0K