03/23 - Pt Teza

Se dă un graf orientat. Se cunosc costurile arcelor. Se citesc 3 noduri x,y,z. Afişaţi gradul interior şi exterior al fiecăruia. Se face o parcurgere în adâncime din nodul x. Care e al 3-lea nod vizitat? Să se verifice dacă se poate ajunge din x în z şi din y în z. Din care se poate ajunge pe un drum mai scurt? x,y,z fac parte din aceeaşi componentă conexă? Din câte noduri se poate ajunge în nodul y?

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int a[100][100],n,m,x,y,z;
int c[100],viz[100]={0},t[100][100],v[100],jj=1,c1[100],u;

void citire()
{int xx,yy,zz,i;
ifstream f("date");
f>>n>>m;
for(i=1;i<=m;i++)
{f>>xx>>yy>>zz;
a[xx][yy]=zz;}
f>>x>>y>>z;}

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

void afisare()
{int i,j;
for(i=1;i<=n;i++){
    for(j=1;j<=n;j++)
        if(a[i][j]!=999)
        cout<<setw(4)<<a[i][j];
       
    cout<<endl;}
cout<<endl;
}

void roy()
{int k,i,j;
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        if(a[i][j]==0)
            a[i][j]=999;

for(k=1;k<=n;k++){
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(a[i][j]>a[i][k]+a[k][j])
                a[i][j]=a[i][k]+a[k][j];
}
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        if(a[i][j]==999)
            a[i][j]=0;
}

int main()
{int s,i,j;
citire();
for(i=1;i<=n;i++)
    {cout<<"d+("<<i<<")=";s=0;
    for(j=1;j<=n;j++)
        if(a[i][j]>0)
            s++;
        cout<<s<<endl;
    }
    cout<<endl;
for(j=1;j<=n;j++)
    {cout<<"d-("<<j<<")=";s=0;
    for(i=1;i<=n;i++)
        if(a[i][j]>0)
            s++;
        cout<<s<<endl;
    }
    cout<<endl;
    cout<<"Parcurgere in adancime din "<<x<<". Al 3-lea nod vizitat este ";
    DF(x);
    cout<<c1[3]<<endl<<endl;
    afisare();
    roy();
    afisare();
    if(a[x][z]>0 && a[y][z]>0)
        if(a[x][z]<a[y][z])
            cout<<"Drum mai scurt din "<<x<<" in "<<z<<endl;
        else cout<<"Drum mai scurt din "<<y<<" in "<<z<<endl;
    else {if(a[x][z]>0)
        cout<<"Se poate ajunge din "<<x<<" in "<<z<<endl;
    if(a[y][z]>0)
        cout<<"Se poate ajunge din "<<x<<" in "<<z<<endl;}
    if(a[x][y] && a[x][z] && a[y][z] && a[y][x] && a[z][x] && a[z][y])
        cout<<x<<", "<<y<<", "<<z<<" fac parte din aceeasi comp tare conexa"<<endl;
    else cout<<x<<", "<<y<<", "<<z<<" NU fac parte din aceeasi comp tare conexa"<<endl;
    cout<<"In nodul "<<y<<" se poate ajunge din nodurile: ";
    for(i=1;i<=n;i++)
        if(a[i][y]>0 && i!=y)
            cout<<i<<" ";
   
}

Fisier

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