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