vineri, 9 mai 2014

Componente conexe a unui graf orientat

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