03/22 - Parcurgeri in adancime/latime grafuri orientate

Sa se verifice daca parcurgerea in adancime coincide cu parcurgerea in latime pentru un graf orientat.

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

void DF(int x)
{cout<<x<<" ";
c1[jj]=x;jj++;
v[x]=1;
for(int i=1;i<=n;i++)
    if(a[x][i]==1 && v[i]==0)
        DF(i);
}

void BF(int x)
{int i,p,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)
    {u++;
    c[u]=i;
    viz[i]=1;}
}
for(i=1;i<=u;i++)
    cout<<c[i]<<" ";
}

int main()
{int i,ok=0;
citire();
cout<<"Parcurgere in adancime"<<endl;
DF(xx);
cout<<endl<<"Parcurgere in latime"<<endl;
BF(xx);
for(i=1;i<=u;i++)
    if(c[i]!=c1[i])
        {cout<<endl<<"NU";ok=1;break;}
if(ok==0)
    cout<<endl<<"DA";
if(ok==1)
{cout<<endl<<"Noduri cu parcurgere identica"<<endl;
    for(i=1;i<=u;i++)
        if(c[i]==c1[i])
            cout<<c[i]<<" ";}
}

Fisier

4 4
1 2
1 3
1 4
2 4
1