#include <iostream>
#include <vector>
#include <queue>
#include <omp.h>
using namespace std;
class Graph {
int V;
vector<vector<int>> adj;
public:
Graph(int V) : V(V) {
adj.resize(V);
}
void addEdge(int u, int v) {
adj[u].push_back(v);
}
void bfs(int start) {
vector<bool> visited(V, false);
queue<int> q;
#pragma omp parallel
{
#pragma omp single
{
q.push(start);
visited[start] = true;
}
while (!q.empty()) {
int u;
#pragma omp critical
{
u = q.front();
q.pop();
}
#pragma omp for
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i];
if (!visited[v]) {
#pragma omp critical
{
q.push(v);
visited[v] = true;
}
}
}
}
}
}
void dfsUtil(int v, vector<bool>& visited) {
visited[v] = true;
cout << v << " ";
#pragma omp parallel for
for (int i = 0; i < adj[v].size(); ++i) {
int u = adj[v][i];
if (!visited[u]) {
dfsUtil(u, visited);
}
}
}
void dfs(int start) {
vector<bool> visited(V, false);
dfsUtil(start, visited);
}
};
int main() {
Graph g(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);
g.addEdge(3, 5);
g.addEdge(4, 5);
cout << "BFS starting from vertex 0: ";
g.bfs(0);
cout << endl;
cout << "DFS starting from vertex 0: ";
g.dfs(0);
cout << endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxvbXAuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpjbGFzcyBHcmFwaCB7CiAgICBpbnQgVjsKICAgIHZlY3Rvcjx2ZWN0b3I8aW50Pj4gYWRqOwoKcHVibGljOgogICAgR3JhcGgoaW50IFYpIDogVihWKSB7CiAgICAgICAgYWRqLnJlc2l6ZShWKTsKICAgIH0KCiAgICB2b2lkIGFkZEVkZ2UoaW50IHUsIGludCB2KSB7CiAgICAgICAgYWRqW3VdLnB1c2hfYmFjayh2KTsKICAgIH0KCiAgICB2b2lkIGJmcyhpbnQgc3RhcnQpIHsKICAgICAgICB2ZWN0b3I8Ym9vbD4gdmlzaXRlZChWLCBmYWxzZSk7CiAgICAgICAgcXVldWU8aW50PiBxOwoKICAgICAgICAjcHJhZ21hIG9tcCBwYXJhbGxlbAogICAgICAgIHsKICAgICAgICAgICAgI3ByYWdtYSBvbXAgc2luZ2xlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHEucHVzaChzdGFydCk7CiAgICAgICAgICAgICAgICB2aXNpdGVkW3N0YXJ0XSA9IHRydWU7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIHdoaWxlICghcS5lbXB0eSgpKSB7CiAgICAgICAgICAgICAgICBpbnQgdTsKCiAgICAgICAgICAgICAgICAjcHJhZ21hIG9tcCBjcml0aWNhbAogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHUgPSBxLmZyb250KCk7CiAgICAgICAgICAgICAgICAgICAgcS5wb3AoKTsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICAjcHJhZ21hIG9tcCBmb3IKICAgICAgICAgICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgYWRqW3VdLnNpemUoKTsgKytpKSB7CiAgICAgICAgICAgICAgICAgICAgaW50IHYgPSBhZGpbdV1baV07CgogICAgICAgICAgICAgICAgICAgIGlmICghdmlzaXRlZFt2XSkgewogICAgICAgICAgICAgICAgICAgICAgICAjcHJhZ21hIG9tcCBjcml0aWNhbAogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBxLnB1c2godik7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB2aXNpdGVkW3ZdID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCiAgICB2b2lkIGRmc1V0aWwoaW50IHYsIHZlY3Rvcjxib29sPiYgdmlzaXRlZCkgewogICAgICAgIHZpc2l0ZWRbdl0gPSB0cnVlOwogICAgICAgIGNvdXQgPDwgdiA8PCAiICI7CgogICAgICAgICNwcmFnbWEgb21wIHBhcmFsbGVsIGZvcgogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgYWRqW3ZdLnNpemUoKTsgKytpKSB7CiAgICAgICAgICAgIGludCB1ID0gYWRqW3ZdW2ldOwogICAgICAgICAgICBpZiAoIXZpc2l0ZWRbdV0pIHsKICAgICAgICAgICAgICAgIGRmc1V0aWwodSwgdmlzaXRlZCk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgdm9pZCBkZnMoaW50IHN0YXJ0KSB7CiAgICAgICAgdmVjdG9yPGJvb2w+IHZpc2l0ZWQoViwgZmFsc2UpOwogICAgICAgIGRmc1V0aWwoc3RhcnQsIHZpc2l0ZWQpOwogICAgfQp9OwoKaW50IG1haW4oKSB7CiAgICBHcmFwaCBnKDYpOwogICAgZy5hZGRFZGdlKDAsIDEpOwogICAgZy5hZGRFZGdlKDAsIDIpOwogICAgZy5hZGRFZGdlKDEsIDMpOwogICAgZy5hZGRFZGdlKDEsIDQpOwogICAgZy5hZGRFZGdlKDIsIDQpOwogICAgZy5hZGRFZGdlKDMsIDUpOwogICAgZy5hZGRFZGdlKDQsIDUpOwoKICAgIGNvdXQgPDwgIkJGUyBzdGFydGluZyBmcm9tIHZlcnRleCAwOiAiOwogICAgZy5iZnMoMCk7CiAgICBjb3V0IDw8IGVuZGw7CgogICAgY291dCA8PCAiREZTIHN0YXJ0aW5nIGZyb20gdmVydGV4IDA6ICI7CiAgICBnLmRmcygwKTsKICAgIGNvdXQgPDwgZW5kbDsKCiAgICByZXR1cm4gMDsKfQo=