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

Sa se verifice daca parcurgerea in adancime coincide cu parcurgerea in latime pentru un graf orientat.

#include<iostream>
#include<fstream>
using namespace std;
int n,a[100][100],m,c[100],viz[100]={0},xx,yy,t[100][100],kk,v[100],jj=1,c1[100],u;
void citire()
{ifstream f("date");
f>>n>>m;
int x,y;
for(int i=1;i<=m;i++)
{f>>x>>y;
a[x][y]=1;}
f>>xx;
}

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

void BF(int x)
{int i,p,v,ii=1,jj=1;
c[1]=x;
viz[x]=1;
p=u=1;
while(p<=u)
{v=c[p];p++;jj=1;
for(i=1;i<=n;i++)
    if(a[v][i]==1 && viz[i]==0)
    {u++;
    c[u]=i;
    viz[i]=1;}
}
for(i=1;i<=u;i++)
    cout<<c[i]<<" ";
}

int main()
{int i,ok=0;
citire();
cout<<"Parcurgere in adancime"<<endl;
DF(xx);
cout<<endl<<"Parcurgere in latime"<<endl;
BF(xx);
for(i=1;i<=u;i++)
    if(c[i]!=c1[i])
        {cout<<endl<<"NU";ok=1;break;}
if(ok==0)
    cout<<endl<<"DA";
if(ok==1)
{cout<<endl<<"Noduri cu parcurgere identica"<<endl;
    for(i=1;i<=u;i++)
        if(c[i]==c1[i])
            cout<<c[i]<<" ";}
}

Fisier

4 4
1 2
1 3
1 4
2 4
1

1) Sa se verifice daca doua noduri x si y fac parte din aceeasi componenta tare conexa. In caz afirmativ, sa se afiseze toate nodurile componentei conexe.

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int n,m,a[100][100];
int viz[100];
int main()
{ifstream f("date");
int i,j,x,k,y,nr=0;
f>>n>>m;
for(i=1;i<=m;i++)
{f>>x>>y;
a[x][y]=1;}
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++)
    if(viz[i]==0)
    {nr++;
    viz[i]=nr;
        for(j=1;j<=n;j++)
            if(a[i][j] && a[j][i])
                viz[j]=nr;
                }
  
cout<<nr<<" componente tare conexe"<<endl;
for(i=1;i<=nr;i++)
{    for(j=1;j<=n;j++)
        if(viz[j]==i)
            cout<<j<<" ";
        cout<<endl;}
int aa,bb;
int ok=0;
cout<<"Cititi nodurile de testat"<<endl;
cin>>aa>>bb;
if(viz[aa]==viz[bb])
    {cout<<"da"<<endl;
ok=1;}
else cout<<"nu";
if(ok)
    for(i=1;i<=n;i++)
        if(viz[i]==viz[aa])
            cout<<i<<" ";
}

Fisier

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

2) Sa se afiseze toate nodurile in care nu intra niciun arc, dar din care ies cel putin t arce.

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int n,m,a[100][100];
int viz[100];
int main()
{ifstream f("date");
int i,j,x,k,y,nr=0,s,t;
f>>n>>m;
for(i=1;i<=m;i++)
{f>>x>>y;
a[x][y]=1;}
cout<<"Cititi t ";
cin>>t;
    for(i=1;i<=n;i++)
        {s=0;
            for(j=1;j<=n;j++)
                s=s+a[i][j];
        a[i][n+1]=s;
        }
       
for(j=1;j<=n;j++)
        {s=0;
            for(i=1;i<=n;i++)
                s=s+a[i][j];
        a[n+1][j]=s;
        }
for(i=1;i<=n+1;i++){
    for(j=1;j<=n+1;j++)
        if(i!=n+1 || j!=n+1)
        cout<<setw(3)<<a[i][j];
    cout<<endl;}
for(i=1;i<=n;i++)
    if(a[n+1][i]==0 && a[i][n+1]>=t)
        cout<<i<<" ";
}

Fisier

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

3) Sa se afiseze toate lanturile elementare de lungime 4.

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

void afisare(int i)
{int j;
for(j=1;j<=i;j++)
    cout<<x[j]<<" ";
cout<<endl;}
   
int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(x[i]==x[j])
        return 0;
if(a[x[i]][x[i-1]]==0 && a[x[i-1]][x[i]]==0)
        return 0;
return 1;
}

void back(int i)
{
for(int j=1;j<=n;j++)
    {x[i]=j;
    if(verif(i))
        if(i==5)
            afisare(i);
        else back(i+1);
}
}

int main()
{ifstream f("date");
int xx,i,j,k,yy;
f>>n>>m;
for(i=1;i<=m;i++)
{f>>xx>>yy;
a[xx][yy]=1;}

for(i=1;i<=n;i++)
{x[1]=i;
back(2);
}
}

Fisier

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

!!!Şi ne-a făcut fericiţi!!!

Să se determine lungimea minimă a lanţurilor de la un nod oarecare la toate celelalte.

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int n,m,a[100][100],viz[100],lg[100],c[100];
void citire()
{int x,y;
ifstream f("date");
f>>n>>m;
for(int i=1;i<=m;i++)
{f>>x>>y;
a[x][y]=a[y][x]=1;}
}

void LEE(int start)
{int st=1,dr=1,varf,i;
c[st]=start;
viz[start]=1;
lg[start]=0;
while(st<=dr)
{varf=c[st];
for(i=1;i<=n;i++)
    if(a[i][varf]==1)
        if(viz[i]==0)
        {c[++dr]=i;
        viz[i]=1;
        lg[i]=lg[varf]+1;}
        st++;
}
}

int main()
{citire();
int start,i;
cout<<"Cititi nodul de start"<<endl;
cin>>start;
LEE(start);
cout<<"Lungimile minile ale lanturilor care pornesc din "<<start<<endl;
for(i=1;i<=n;i++)
    cout<<"catre "<<i<<": "<<lg[i]<<endl;
}

Fişier

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

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int a[100][100],n,m;
void citire()
{ifstream f("date");
f>>n>>m;
int x,y,z,i,j;
for(i=1;i<=m;i++)
{f>>x>>y>>z;
a[x][y]=z;}
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        if(a[i][j]==0)
            a[i][j]=999;
}
void afisare()
{int i,j;
for(i=1;i<=n;i++){
    for(j=1;j<=n;j++)
        cout<<setw(4)<<a[i][j];
    cout<<endl;}
cout<<endl;
}
void roy()
{int k,i,j;
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];
            afisare();}
}
int main()
{citire();
roy();
afisare();
}

Fisier

4 6
1 2 10
2 3 5
2 4 7
3 4 1
4 1 3
4 2 20

Algo

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

int main()
{ifstream f("date");
int i,j,x,k,y;
f>>n>>m;
for(i=1;i<=m;i++)
{f>>x>>y;
a[x][y]=1;}
cout<<"Matricea de adiacenta"<<endl;
for(i=1;i<=n;i++){
    for(j=1;j<=n;j++)
        cout<<setw(3)<<a[i][j];
    cout<<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;
cout<<endl<<"Matricea drumurilor"<<endl;
for(i=1;i<=n;i++){
    for(j=1;j<=n;j++)
        cout<<setw(3)<<a[i][j];
    cout<<endl;}
}

Fisier

6 11
1 2
1 3
1 4
1 5
2 3
2 5
3 2
3 4
3 5
3 6
6 4

Determinarea componentelor TARE! conexe

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int n,m,a[100][100];
int viz[100];
int main()
{ifstream f("date");
int i,j,x,k,y,nr=0;
f>>n>>m;
for(i=1;i<=m;i++)
{f>>x>>y;
a[x][y]=1;}
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;}

for(i=1;i<=n;i++)
    if(viz[i]==0)
    {nr++;viz[i]=nr;
        for(j=1;j<=n;j++)
            if(a[i][j] && a[j][i])
                viz[j]=nr;
                }
   
cout<<nr<<" componente tare conexe"<<endl;
for(i=1;i<=nr;i++)
{    for(j=1;j<=n;j++)
        if(viz[j]==i)
            cout<<j<<" ";
        cout<<endl;}

}

Fisier

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