6932436

1739454

1235764

@ Casa Pariurilor

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int a[100][100],n,m,c[100],viz[100],x,y;

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

void DF(int x, int &k)
{int i;
c[k]=x;
k++;
for(i=1;i<=n;i++)
    if(a[x][i]!=0 && viz[i]==0)
    {viz[i]=1;
    DF(i,k);}
}

int main()
{int i,j,k,p=1;
citire();
cout<<"a) Nodurile pentru care gradul exterior este mai mare decat gradul interior"<<endl;
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        a[i][n+1]+=a[i][j];
   
for(j=1;j<=n;j++)
    for(i=1;i<=n;i++)
        a[n+1][j]+=a[i][j];
   
/*for(i=1;i<=n+1;i++)
{    for(j=1;j<=n+1;j++)
        cout<<setw(3)<<a[i][j];
    cout<<endl;}*/
   
for(i=1;i<=n;i++)
    if(a[n+1][i]<a[i][n+1])
        cout<<i<<" ";
    cout<<endl<<endl;
for(k=1;k<=n;k++)
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(a[i][k] && a[k][j])
                a[i][j]=1;
/*for(i=1;i<=n;i++)
{    for(j=1;j<=n;j++)
        cout<<setw(3)<<a[i][j];
    cout<<endl;}*/
if(a[x][y] && a[y][x])
    cout<<"b) "<<x<<" si "<<y<<" fac parte din aceeasi componenta tare conexa";
else cout<<"b) "<<x<<" si "<<y<<" NU fac parte din aceeasi componenta tare conexa";
DF(x,p);
cout<<endl<<endl<<"c) Ultimul nod vizitat in adancime pornind din "<<x<<" este "<<c[p-1];
}

Fisier

5 8
1 3
1 4
1 5
2 1
3 2
2 4
4 5
5 4
4 2

Algo.

#include <iostream>
#include <fstream>
using namespace std;
int a[20][20],d[20],viz[20],n,m,start;
void citire ()
{
    int i,x,y,c;
    ifstream fin ("graf.in");
    fin>>n>>m>>start;
    for (i=1;i<=m;i++){
        fin>>x>>y>>c;
        a[x][y]=c;
    }
}
void drum_minim ()
{
    int i,j,minim,nodminim;
    viz[start]=1;
    for (i=1;i<=n;i++){
        if (a[start][i]) d[i]=a[start][i];
        else d[i]=99999;
    }
    d[start]=0;
    for (i=1;i<=n;i++){
        minim=99999;
        for (j=1;j<=n;j++){
            if (!viz[j] && d[j]<minim){
                minim=d[j];
                nodminim=j;
            }
        }
        viz[nodminim]=1;
        for (j=1;j<=n;j++){
            if (a[nodminim][j] && d[j]>minim+a[nodminim][j])
                d[j]=minim+a[nodminim][j];
        }
    }
}
int main ()
{
    int i;
    citire ();
    drum_minim ();
    for (i=1;i<=n;i++){
        cout<<"Distanta minima dintre "<<start<<" si "<<i;
        cout<<" este "<<d[i]<<'\n';
       
    }
    return 0;
}

Fişier

8 13 2
1 2 1
1 3 10
2 3 6
2 4 1
4 3 3
4 6 5
4 5 1
5 3 1
3 8 10
6 5 2
6 7 3
7 8 1
5 8 25

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