Orar semigroup #2

Orar semigroup #2

3/14 - Algoritmul Roy-Warshall - Drum Minim cu costuri

#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

marți, 13 martie 2012 by DlMuresan
Categories: , , | Leave a comment

03/05 - Matricea Drumurilor, Comp Tare Conexe

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

duminică, 4 martie 2012 by DlMuresan
Categories: , | Leave a comment

02/28 - Parcurgeri de tot felul

Se parcurge un graf in adancime si latime plecand dintr-un acelasi nod x. Sa se verifice daca nodurile sunt vizitate in aceeasi ordine.

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

void DF(int x)
{cout<<x<<" ";
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 k)
{int c[100],i,p,u,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)
    {t[ii][jj]=i;
    jj++;
        u++;
       
    c[u]=i;
    viz[i]=1;}
    if(t[ii][jj-1]!=0)
    ii++;
}
for(i=1;i<=u;i++)
    cout<<c[i]<<" ";
//cout<<endl;
}

int main()
{
    citire();
cout<<"Parcurgere in adancime"<<endl;
DF(1);
cout<<endl<<"Parcurgere in latime"<<endl;
BF(1,0);
}

duminică, 26 februarie 2012 by DlMuresan
Categories: , , | Leave a comment

02/24 - Probleme grafuri orientate

2. Se citesc din fisierul graf.in n (nr noduri), m (nr. arce) si arcele unui graf orientat.
A) Sa se construiasca matricea varfuri-arce
B) Sa se afiseze listele de vecini
C) Sa se afiseze gradul exterior si interior al fiecarui nod.
D) Pornind de la matricea varfuri-arce sa se construiasca matricea de adiacente.

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int b[10][10],a[10][10];
int main()
{ifstream f("date");
int x,y,n,m,i,j,k,p,ii,d1,d2,u1,u2;
f>>n>>m;
for(j=1;j<=m;j++)
{f>>x>>y;
b[x][j]=1;
b[y][j]=-1;}
cout<<"Matricea varfuri-arce"<<endl;
for(i=1;i<=n;i++)
    {for(j=1;j<=m;j++)
        cout<<setw(3)<<b[i][j];
    cout<<endl;
    }
    cout<<endl<<"Extremitati initiale"<<endl;
for(i=1;i<=n;i++)
{    cout<<"Nodul "<<i<<": ";
    for(j=1;j<=m;j++)
        {
        if(b[i][j]==1)
            for(ii=1;ii<=n;ii++)
                if(b[ii][j]==-1)
                    cout<<ii<<" ";
    }
        cout<<endl;}
cout<<endl;
cout<<"Extremitati finale"<<endl;
for(i=1;i<=n;i++)
{    cout<<"Nodul "<<i<<": ";
    for(j=1;j<=m;j++)
        {
        if(b[i][j]==-1)
            for(ii=1;ii<=n;ii++)
                if(b[ii][j]==1)
                    cout<<ii<<" ";
        }
        cout<<endl;}
cout<<endl;
cout<<"Gradele varfurilor"<<endl;
for(i=1;i<=n;i++)
{d1=d2=0;
    for(j=1;j<=m;j++)
        if(b[i][j]==1)
            d1++;
        else if(b[i][j]==-1)
            d2++;
    cout<<"d+("<<i<<")="<<d1;
    cout<<"  ";
    cout<<"d-("<<i<<")="<<d2;
    cout<<endl;
}
cout<<endl;
cout<<"Matricea de adiacente"<<endl;
for(j=1;j<=m;j++)
{//u1=u2=0;
    for(i=1;i<=n;i++)
        {if(b[i][j]==1)
            u1=i;
        if(b[i][j]==-1)
            u2=i;}
        a[u1][u2]=1;
        }
   
for(i=1;i<=n;i++)
{    for(j=1;j<=n;j++)
        cout<<setw(3)<<a[i][j];
    cout<<endl;}
       
}

joi, 23 februarie 2012 by DlMuresan
Categories: , | Leave a comment

02/22 - Grafuri orientate

Se citeste un graf orientat. Sa se afiseze nodul interior si exterior al fiecarui nod. Sa se afiseze predecesorii si succesorii fiecarui nod. Sa se afiseze nodurile izolate. Sa se afiseze arcele incidente cu un nod dat.

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int main()
{ifstream f("date");
int n,m,i,j,s2,s1,x,y,a[10][10]={0},ok;
f>>n>>m;
for(i=1;i<=m;i++)
    {f>>x>>y;
    a[x][y]=1;}
for(i=1;i<=n;i++)
{s1=0;s2=0;
    for(j=1;j<=n;j++)
        {s1+=a[i][j];
        s2+=a[j][i];}
    cout<<"Nodul "<<i<<" are gradul exterior "<<s1<<endl;
    cout<<"Nodul "<<i<<" are gradul interior "<<s2<<endl;
    cout<<endl;
}
for(i=1;i<=n;i++)
    {cout<<"Succesorii lui "<<i<<": ";
        for(j=1;j<=n;j++)
            if(a[i][j]==1)
                cout<<j<<" ";
            cout<<endl;
    }
    cout<<endl;
for(i=1;i<=n;i++)
    {cout<<"Predecesorii lui "<<i<<": ";
        for(j=1;j<=n;j++)
            if(a[j][i]==1)
                cout<<j<<" ";
            cout<<endl;
    }
cout<<"Noduri izolate: ";
for(i=1;i<=n;i++)
{ok=1;
for(j=1;j<=n;j++)
    if(a[i][j]!=0 || a[j][i]!=0)
        ok=0;
if(ok==1)
    cout<<i<<" ";
}
cout<<endl<<endl;
for(i=1;i<=n;i++)
{cout<<"Arce incidente cu "<<i<<": ";
for(j=1;j<=n;j++)
{    if(a[i][j]==1)
        cout<<i<<" "<<j<<"   ";
    if(a[j][i]==1)
        cout<<j<<" "<<i<<"   ";}
    cout<<endl;
}

}

marți, 21 februarie 2012 by DlMuresan
Categories: , | Leave a comment