02/11 - Parcurgere in latime

1. Folosind algoritmul de parcurgere in latime a unui graf, (BF) sa se realizeze urmatoarele cerinte:
a) sa se verifice daca un graf e conex
b) sa se verifice daca se poate ajunge de la nodul x la nodul y
c) sa se afiseze componenetele conexe ale grafului
d) pornind cu parcurgerea din nodul x, sa se afiseze nivelul fiecarui nod in arborele obtinut 

#include<iostream>
#include<fstream>
using namespace std;
int n,a[100][100],m,viz[100]={0},xx,yy,t[100][100],kk;
void citire()
{ifstream f("gf");
f>>n>>m;
int x,y;
for(int i=1;i<=m;i++)
{f>>x>>y;
a[x][y]=a[y][x]=1;}
f>>xx>>yy>>kk;
}

void BF(int x, int k)
{int c[100],i,p,u,v,ii=1,jj=1;
c[1]=x;
viz[x]=1;
p=u=1;
while(p<=u)
{v=c[p];p++;jj=1;
for(i=1;i<=n;i++)
    if(a[v][i]==1 && viz[i]==0)
    {t[ii][jj]=i;
    jj++;
        u++;// afisare nod pentru determinarea  ordinii de parcurgere
    c[u]=i;
    viz[i]=1;}
    if(t[ii][jj-1]!=0)
    ii++;
}
for(i=1;i<=u;i++)
    cout<<c[i]<<" ";
//cout<<endl;
}


int main()
{citire();
int k=0,i;
for(i=1;i<=n;i++)
    if(!viz[i])
    {k++;
    BF(i,k);cout<<endl;
    }
if(k!=1)
    cout<<endl<<"Graful nu e conex"<<endl;
else cout<<endl<<"Graful e conex"<<endl;
cout<<k<<" componente conexe"<<endl;
for(i=1;i<=n;i++)
    viz[i]=0;
cout<<endl;
cout<<"Parcurgerea din "<<xx<<endl;
BF(xx,0);
cout<<endl;
if(viz[yy]!=0)
    cout<<"Se poate ajunge din "<<xx<<" in "<<yy<<endl;
else cout<<"Nu se poate ajunge din "<<xx<<" in "<<yy<<endl;
for(i=1;i<=n;i++)
    viz[i]=0;
cout<<endl;
cout<<"Componentele conexe"<<endl;
for(i=1;i<=n;i++)
    if(viz[i]==0)
        {BF(i,0);cout<<endl;}
    cout<<endl;cout<<endl;
cout<<"Parcurgere in latime din nodul ";
BF(1,0);
cout<<endl;
t[0][1]=1;
for(i=0;i<=n;i++)
    {if(t[i][1]!=0)
        cout<<"Nivelul "<<i<<": ";
for(int j=1;j<=n;j++)
    if(t[i][j]!=0)
    cout<<t[i][j]<<" ";
    cout<<endl;}
 
}

Fisier

7 7
2 7
1 2
1 5
2 6
3 4
4 7
5 6
1 7
1