Arborescenta

#include<fstream.h>
#include<conio.h>
int a[20][20],b[20][20],s[20],gasit,ok,radacina,n,i,j,suma,r;

void citire(char nume[10],int a[20][20],int& n)
{
fstream f(nume,ios::in);
int i,j;
f>>n;
while (f>>i>>j) a[i][j]=1;
f.close();
}

void df(int nod)
{
int k;s[nod]=1;
for(k=1;k<=n;k++)
if(a[nod][k]==1 || a[k][nod]==1)
{a[k][nod]=a[nod][k]=0;
if (s[k]==0) df(k);
else gasit=1;
}
}

void df1(int nod)
{
int k;s[nod]=1;
for(k=1;k<=n;k++)
if (a[nod][k]==1 && s[k]==0) df1(k);
}

void main()
{
citire(“graf.txt”,a,n);cout<<“n->”<<n<<endl;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) b[i][j]=a[i][j];
df(1);
for(i=1;i<=n;i++) suma+=s[i];
if(suma!=n) cout<<“nu este conex”<<endl;
else cout<<“este conex”<<endl;
if(gasit) cout<<“are cel putin un ciclu”<<endl;
else cout<<“nu are cicluri”;
if (suma==n && !gasit)
{cout<<“este arbore”<<endl;
ok=1;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) a[i][j]=b[i][j];
if (ok)
{r=1;
do
{suma=0;for(i=1;i<=n;i++)s[i]=0;
df1(r);
for(i=1;i<=n;i++) suma+=s[i];
if (suma==n)
{cout<<“radacina este “<<r<<endl<<“este arborescenta”<<endl;
radacina=1;
}
else r++;
}while (!radacina && r<=n);
if(!radacina) cout<<“nu are radacina”;
}
getch();
}