Fiind dat un graf orintat, sa se determine componente tare conexa careia ii apartine un varf x citit de la tastatura.
Aspect teoretic
Definitie: Un graf orientat G=(X,U) este tare conex daca pentru oricare x si y exista un drum de la x la y precum si un drum de la y la x.
Definitie: Fiind dat un graf orintat G=(X,U), se numeste componenta tare conexa a lui G, un subgraf G1=(X1,U1), tare conex, si maximal in raport cu aceasta proprietate (pentru orice nod x apartinand lui X-X1, subgraful indus de X1 U {x} nu mai este tare conex)
#include<fstream.h>
int a[20][20],n,m,suc[100],prec[100],x;
void dfsuc(int nod)
{suc[nod]=x;
for(int k=1;k<=n;k++)
if(a[nod][k]==1&&suc[k]==0)
dfsuc(k);
}
void dfprec(int nod)
{ prec[nod]=x;
for(int k=1;k<=n;k++)
if(a[k][nod]==1&&prec[k]==0)
dfprec(k);
}
void main()
{int y,j;
fstream f;
f.open("comptare.in",ios::in);
if(f)
cout<<"bine"<<endl;
else
cout<<"eroare !";
f>>n>>m;
for(int i=1;i<=m;i++)
{f>>x>>y;
a[x][y]=1;}
cout<<endl<<"matricea de adiacenta"<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<endl;}
cout<<"x=";cin>>x;
dfsuc(x);
cout<<endl<<"succesorii lui "<<x<<endl;
for(i=1;i<=n;i++)
if(suc[i]!=0)
cout<<i<<" ";
dfprec(x);
cout<<endl<<"Predecesorii lui "<<x<<endl;
for(i=1;i<=n;i++)
if(prec[i]!=0)
cout<<i<<" ";
cout<<endl<<"componenta tare conexa in care se gaseste "<<x<<" este "<<endl;
for(i=1;i<=n;i++)
if(prec[i]==suc[i]&&suc[i]!=0)
cout<<i<<" ";}
Niciun comentariu:
Trimiteți un comentariu