#include<iostream>
using namespace std;
struct node
{
int x;
node*link;
};
node*r = NULL;
node*f = NULL;
void enq(int y)
{
node* obj = new node;
obj->x = y;
obj->link = NULL;
if (r == NULL && f == NULL)
{
f = r = obj;
return;
}
else
{
r->link = obj;
r = obj;
}
}
int isempty()
{
return (f == NULL);
}
int deq()
{
int data;
if (isempty())
{
cout << "Queue is empty\n";
return 0;
}
else
{
data = f->x;
f = f->link;
if(f==NULL)
r=NULL; // 'r' wasnt being reinitialized to NULL!!!
return data;
}
}
int mat[30][30] = { 0 }, visit[30] = { 0 }, q[30];
void bfs(int k,int v)
{
int i, u;
enq(k);
while (!isempty())
{
u = deq();
cout << u+1 << endl;
visit[u] = 1;
for (i = 0; i < v; i++)
{
if (!visit[i] && mat[u][i]) // "[u][i]" instead of [k][i]
{
//cout<<"++++"<<i+1<<endl;
enq(i);
}
}
}
}
void bfst(int v)
{
/*for(int i=0;i<v;i++,cout<<endl)
for(int j=0;j<v;j++)
cout<<mat[i][j]<<"\t";*/
int i;
for (i = 0; i < v; i++)
{
if (!visit[i])
bfs(i, v);
}
}
int main()
{
int i, j, k, v, e, l, m;
cout << "Enter the number of vertices and edges\n";
cin >> v >> e;
cout << "Enter the adjacenecy matrix\n";
for (i = 0; i < e; i++)
{
cin >> l >> m;
mat[l - 1][m - 1] = 1;
mat[m - 1][l - 1] = 1;
}
bfst(v);
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3Qgbm9kZQp7CiAgICBpbnQgeDsKICAgIG5vZGUqbGluazsKfTsKCm5vZGUqciA9IE5VTEw7Cm5vZGUqZiA9IE5VTEw7Cgp2b2lkIGVucShpbnQgeSkKCnsKCiAgICBub2RlKiBvYmogPSBuZXcgbm9kZTsKCiAgICBvYmotPnggPSB5OwoKICAgIG9iai0+bGluayA9IE5VTEw7CgogICAgaWYgKHIgPT0gTlVMTCAmJiBmID09IE5VTEwpCiAgICB7CiAgICAgICAgZiA9IHIgPSBvYmo7CiAgICAgICAgcmV0dXJuOwogICAgfQoKICAgIGVsc2UKICAgIHsKICAgICAgICByLT5saW5rID0gb2JqOwogICAgICAgIHIgPSBvYmo7CgogICAgfQp9CgppbnQgaXNlbXB0eSgpCnsKICAgIHJldHVybiAoZiA9PSBOVUxMKTsKfQoKaW50IGRlcSgpCnsKICAgIGludCBkYXRhOwoKICAgIGlmIChpc2VtcHR5KCkpCiAgICB7CiAgICAgICAgY291dCA8PCAiUXVldWUgaXMgZW1wdHlcbiI7CiAgICAgICAgcmV0dXJuIDA7CiAgICB9CgogICAgZWxzZQogICAgewogICAgICAgIGRhdGEgPSBmLT54OwogICAgICAgIGYgPSBmLT5saW5rOwogICAgICAgIGlmKGY9PU5VTEwpCiAgICAgICAgICAgICAgcj1OVUxMOyAgICAgICAgICAgLy8gJ3InIHdhc250IGJlaW5nIHJlaW5pdGlhbGl6ZWQgdG8gTlVMTCEhIQogICAgICAgIHJldHVybiBkYXRhOwogICAgfQoKfQoKCmludCBtYXRbMzBdWzMwXSA9IHsgMCB9LCB2aXNpdFszMF0gPSB7IDAgfSwgcVszMF07Cgp2b2lkIGJmcyhpbnQgayxpbnQgdikKCnsKICAgIGludCBpLCB1OwoKICAgICAgZW5xKGspOwoKICAgIHdoaWxlICghaXNlbXB0eSgpKQoKewogICAgICAgIHUgPSBkZXEoKTsKCmNvdXQgPDwgdSsxIDw8IGVuZGw7CgogICAgICAgIHZpc2l0W3VdID0gMTsKCiAgICAgICAgZm9yIChpID0gMDsgaSA8IHY7IGkrKykKCiAgICAgICAgewoKICAgICAgICAgICAgaWYgKCF2aXNpdFtpXSAmJiBtYXRbdV1baV0pICAgICAvLyAiW3VdW2ldIiBpbnN0ZWFkIG9mIFtrXVtpXQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAvL2NvdXQ8PCIrKysrIjw8aSsxPDxlbmRsOwogICAgICAgICAgICAgICAgZW5xKGkpOwogICAgICAgICAgICB9CgogICAgICAgIH0KCiAgICB9Cgp9Cgp2b2lkIGJmc3QoaW50IHYpCgp7CgkvKmZvcihpbnQgaT0wO2k8djtpKyssY291dDw8ZW5kbCkKCQlmb3IoaW50IGo9MDtqPHY7aisrKQoJCQljb3V0PDxtYXRbaV1bal08PCJcdCI7Ki8KICAgIGludCBpOwoKICAgIGZvciAoaSA9IDA7IGkgPCB2OyBpKyspCgogICAgewoKICAgICAgICBpZiAoIXZpc2l0W2ldKQoJCQogICAgICAgICAgICBiZnMoaSwgdik7CiAgICAgICAgICAgIAoKICAgIH0KCn0KaW50IG1haW4oKQp7CiAgICBpbnQgaSwgaiwgaywgdiwgZSwgbCwgbTsKCmNvdXQgPDwgIkVudGVyIHRoZSBudW1iZXIgb2YgdmVydGljZXMgYW5kIGVkZ2VzXG4iOwoKICAgIGNpbiA+PiB2ID4+IGU7CgoKCiAgICBjb3V0IDw8ICJFbnRlciB0aGUgYWRqYWNlbmVjeSBtYXRyaXhcbiI7CgogICAgZm9yIChpID0gMDsgaSA8IGU7IGkrKykKICAgIHsKICAgICAgICBjaW4gPj4gbCA+PiBtOwogICAgICAgIG1hdFtsIC0gMV1bbSAtIDFdID0gMTsKICAgICAgICBtYXRbbSAtIDFdW2wgLSAxXSA9IDE7CiAgICB9CiAgICBiZnN0KHYpOwoKICAgIHJldHVybiAwOwp9