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