Probleme rezolvate

Probleme rezolvate


1.

Matricea lanturilor - algoritmul Roy-Warshall Se citeste un graf neorientat cu n noduri si m muchii dat prin vectorul muchiilor. Sa se construiasca o matricea existentei lanturilor(a[i][j] este 1 daca exista lant de la i la j si 0 in caz contrar). Ex: Pentru graful din imagine se obtine matricea lanturilor urmatoare: 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0

#include<fstream.h>
int k,m,n,x[100],a[100][100],p[100];

fstream f("graf.in",ios::in);
fstream g("graf.out",ios::out);

void citire()
 {int x,y;
  f>>n>>m;
  for(int i=1;i<=m;i++)
   {f>>x>>y;
    a[x][y]=1;
    a[y][x]=1;
   }
 }
void rw()
 {int i, j, k;
  for(k=1;k<=n;k++)
   for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
   if(i!=j)
   if(a[i][j]==0)
   a[i][j]=a[i][k]*a[k][j];
 }
 void afis()
  {for(int i=1;i<=n;i++)
    {g<<endl;
     for(int
     j=1;j<=n;j++)
      g<<a[i][j]<<" ";
   }
  }

 void main()
  {citire();
   rw();
   afis();
  }

2.

Se da un graf neorientat cu n varfuri si m muchii, citit prin vectorul muchiilor. Sa se afiseze pe linii separate componentele sale conexe. 
Ex: Pentru graful alaturat se vor afisa urmatoarele componente conexe: 
1 2 4 5 
3 7 
6

#include<fstream.h>

int a[100][100],n,m,x[100],p[100];

void citire()
{ int i,l,c;
  ifstream f("g.in");
  f>>n>>m;
  for(i=1;i<=m;i++)
  { f>>l>>c;
    a[l][c]=1;
    a[c][l]=1;
  }
}

void bf(int k)
{ int i,s,d;
  x[1]=k;
  p[k]=1;
  s=d=1;
  while(s<=d)
  { for(i=1;i<=n;i++)
     if(a[x[s]][i]==1 && !p[i])
 { d++;
   x[d]=i;
   p[i]=1;
 }
    s++;
  }
  for(i=1;i<=d;i++) cout<<x[i]<<" ";
  cout<<endl;
}

void main()
{ citire();
  int i;
  for(i=1;i<=n;i++)
    if(!p[i]) bf(i);
}