//
// main.cpp
// BFS Graph
//
// Created by Himanshu on 26/08/21.
//
#include <iostream>
#include <queue>
using namespace std;
//s= source
//n = number of nodes in graph
void BFS (int s, int n, vector<int> graph[]) {
if (s == 0) {
return;
}
int vis[n+1];
queue<int> qu;
for (int i=1; i<=n; i++) {
vis[i] = 0;
}
qu.push(s);
vis[s] = 1;
cout<<"BFS:"<<endl;
cout<<s<<endl;
while (!qu.empty()) {
int node = qu.front();
qu.pop();
for (int i=0; i<graph[node].size(); i++) {
int j = graph[node][i];
if (vis[j] == 0) {
vis[j] = 1;
qu.push(j);
cout<<j<<" ";
}
}
cout<<endl;
}
cout<<endl;
}
int main() {
int s = 1, n = 5;
vector<int> graph[n+1];
graph[1].push_back(2);
graph[1].push_back(3);
graph[2].push_back(1);
graph[2].push_back(4);
graph[3].push_back(1);
graph[3].push_back(5);
graph[4].push_back(2);
graph[4].push_back(5);
graph[5].push_back(3);
graph[5].push_back(4);
cout<<"Graph:"<<endl;
for (int i=1; i<=n; i++) {
cout<<i<<": ";
for (int j=0; j<graph[i].size(); j++) {
cout<<graph[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
BFS(s, n, graph);
return 0;
}
Ly8KLy8gIG1haW4uY3BwCi8vICBCRlMgR3JhcGgKLy8KLy8gIENyZWF0ZWQgYnkgSGltYW5zaHUgb24gMjYvMDgvMjEuCi8vCiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHF1ZXVlPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy9zPSBzb3VyY2UKLy9uID0gbnVtYmVyIG9mIG5vZGVzIGluIGdyYXBoCnZvaWQgQkZTIChpbnQgcywgaW50IG4sIHZlY3RvcjxpbnQ+IGdyYXBoW10pIHsKICAgIGlmIChzID09IDApIHsKICAgICAgICByZXR1cm47CiAgICB9CiAgICBpbnQgdmlzW24rMV07CiAgICBxdWV1ZTxpbnQ+IHF1OwogICAgCiAgICBmb3IgKGludCBpPTE7IGk8PW47IGkrKykgewogICAgICAgIHZpc1tpXSA9IDA7CiAgICB9CiAgICBxdS5wdXNoKHMpOwogICAgdmlzW3NdID0gMTsKICAgIGNvdXQ8PCJCRlM6Ijw8ZW5kbDsKICAgIGNvdXQ8PHM8PGVuZGw7CiAgICB3aGlsZSAoIXF1LmVtcHR5KCkpIHsKICAgICAgICBpbnQgbm9kZSA9IHF1LmZyb250KCk7CiAgICAgICAgcXUucG9wKCk7CiAgICAgICAgZm9yIChpbnQgaT0wOyBpPGdyYXBoW25vZGVdLnNpemUoKTsgaSsrKSB7CiAgICAgICAgICAgIGludCBqID0gZ3JhcGhbbm9kZV1baV07CiAgICAgICAgICAgIGlmICh2aXNbal0gPT0gMCkgewogICAgICAgICAgICAgICAgdmlzW2pdID0gMTsKICAgICAgICAgICAgICAgIHF1LnB1c2goaik7CiAgICAgICAgICAgICAgICBjb3V0PDxqPDwiICI7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgY291dDw8ZW5kbDsKICAgIH0KICAgIGNvdXQ8PGVuZGw7Cn0KCgppbnQgbWFpbigpIHsKICAgIGludCBzID0gMSwgbiA9IDU7CiAgICB2ZWN0b3I8aW50PiBncmFwaFtuKzFdOwogICAgZ3JhcGhbMV0ucHVzaF9iYWNrKDIpOwogICAgZ3JhcGhbMV0ucHVzaF9iYWNrKDMpOwogICAgZ3JhcGhbMl0ucHVzaF9iYWNrKDEpOwogICAgZ3JhcGhbMl0ucHVzaF9iYWNrKDQpOwogICAgZ3JhcGhbM10ucHVzaF9iYWNrKDEpOwogICAgZ3JhcGhbM10ucHVzaF9iYWNrKDUpOwogICAgZ3JhcGhbNF0ucHVzaF9iYWNrKDIpOwogICAgZ3JhcGhbNF0ucHVzaF9iYWNrKDUpOwogICAgZ3JhcGhbNV0ucHVzaF9iYWNrKDMpOwogICAgZ3JhcGhbNV0ucHVzaF9iYWNrKDQpOwogICAgCiAgICBjb3V0PDwiR3JhcGg6Ijw8ZW5kbDsKICAgIGZvciAoaW50IGk9MTsgaTw9bjsgaSsrKSB7CiAgICAgICAgY291dDw8aTw8IjogIjsKICAgICAgICBmb3IgKGludCBqPTA7IGo8Z3JhcGhbaV0uc2l6ZSgpOyBqKyspIHsKICAgICAgICAgICAgY291dDw8Z3JhcGhbaV1bal08PCIgIjsKICAgICAgICB9CiAgICAgICAgY291dDw8ZW5kbDsKICAgIH0KICAgIGNvdXQ8PGVuZGw7CiAgICBCRlMocywgbiwgZ3JhcGgpOwogICAgcmV0dXJuIDA7Cn0K