01/23 - Probleme

1. Se dau două grafuri. Să se verifice dacă al doilea este graf parţial/subgraf al primului. Pentru subgraf se citesc, în ordine: nb, mb, vârfurile şi apoi muchiile.

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int n,m,i,ua[10][10],ub[10][10],na,nb,ma,mb,ok=1,ok1=1,v[10];
int a,b,c,j,k;
int main()
{ifstream fa("a");
ifstream fb("b");
fa>>na>>ma;
fb>>nb>>mb;
if(na!=nb)
 {cout<<"nu este graf partial"<<endl;
 ok=0;}

if(nb>=na)
 {cout<<"nu este subgraf"<<endl;}
for(i=1;i<=ma;i++)
{fa>>a>>b;
ua[a][b]=ua[b][a]=1;}
for(i=1;i<=nb;i++)
 {fb>>a;
 v[a]=1;}
for(i=1;i<=mb;i++)
{fb>>a>>b;
ub[a][b]=ub[b][a]=1;}
for(i=1;i<=na;i++)
 {for(j=1;j<=na;j++)
  cout<<setw(3)<<ua[i][j]<<ub[i][j];
 cout<<endl;}
if(ok==1)
{
for(i=1;i<=na;i++)
 for(j=1;j<=na;j++)
  if(ub[i][j]==1 && ua[i][j]==0)
  {cout<<"nu este graf partial"<<endl;
  ok=0;}
}
if(ok==1)cout<<"este graf partial";
for(i=1;i<=na;i++)
 for(j=1;j<=na;j++)
  if(v[i]==1 && v[j]==1)
  if(ub[i][j]!=ua[i][j])
  {cout<<"nu este subgraf"<<endl;
  ok1=0;
  return 0;}
if(ok1==1)cout<<"este subgraf";
}

Fişiere

7 6
1 2
1 5
1 6
2 3
2 6
6 7

7 5
1 2
1 5
2 3
2 6
6 4

2. Se citeşte dintr-un fişier numărul de noduri, muchii şi muchiile unui graf. Să se afişeze: a) nodurile de grad maxim; b) lanţurile elementare L=2 ce pornesc din k; c) lanţurile elementare L=3 ce pornesc din x şi se termină în y; d) ciclurile elementare L=3 ce conţin nodul u; e) verificaţi dacă graful e complet; f) toate lanţurile elementare care pornesc din x şi se termină în y; câte sunt si care e lungimea maximă?

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int n,m,i,u[100][100],ok=1,ok1=1,v[100],nr,xx[100],ii=2,mm[100],ms=0;
int a,b,c,j,k,maxi=0,x,y,uu;

void afisare(int i)
{int j;
nr++;
for(j=1;j<=i;j++)
    cout<<xx[j]<<" ";
cout<<endl;
}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(xx[j]==xx[i])
        return 0;
return 1;
}

void back(int i)
{int j;
for(j=1;j<=n;j++)
{if(u[xx[i-1]][j]==1)
    {xx[i]=j;
if(verif(i))
    if(xx[i]==y)
        {afisare(i);
    if(i>ms)ms=i;
    for(int o=1;o<=i;o++)
        mm[o]=xx[o];
        }
    else back(i+1);
    }
}
}

int main()
{ifstream f("graf");
f>>n>>m;
for(i=1;i<=m;i++)
{f>>a>>b;
u[a][b]=u[b][a]=1;}
f>>k>>x>>y>>uu;
for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
  v[i]+=u[i][j];
for(i=1;i<=n;i++)
 if(v[i]>maxi)
  maxi=v[i];
cout<<"Nodurile de grad maxim"<<endl;
for(i=1;i<=n;i++)
 if(v[i]==maxi)
  cout<<i<<" ";
 cout<<endl<<endl;
cout<<"Lanturi de L=2 care pornesc din "<<k<<endl;
for(i=1;i<=n;i++)
 if(u[k][i]==1)
  for(j=1;j<=n;j++)
   if(u[i][j]==1 && j!=k)
    cout<<k<<" "<<i<<" "<<j<<endl;
   cout<<endl;
cout<<"Lanturi de L=3 care pornesc din "<<x<<" si se termina in "<<y<<endl;
for(i=1;i<=n;i++)
 if(u[x][i]==1)
  for(j=1;j<=n;j++)
   if(u[i][j]==1)
    for(int ii=1;ii<=n;ii++)
     if(u[j][ii]==1 && ii==y)
      cout<<x<<" "<<i<<" "<<j<<" "<<ii<<endl;
cout<<endl<<"Cicluri elementare de L=3 ce contin nodul "<<uu<<endl;
for(i=1;i<=n;i++)
 if(u[uu][i]==1)
  for(j=1;j<=n;j++)
   if(u[i][j]==1)
    for(int ii=1;ii<=n;ii++)
     if(u[j][ii]==1 && ii==uu)
      cout<<uu<<" "<<i<<" "<<j<<" "<<ii<<endl;
cout<<endl;
if(m==n*(n-1)/2)
    cout<<"Graful e complet"<<endl<<endl;
else cout<<"Graful nu e complet"<<endl<<endl;
cout<<"Lanturile elementare ce pornesc din "<<x<<" si se termina in "<<y<<endl;
xx[1]=x;
back(2);
cout<<nr<<" lanturi. Cel mai mare: ";
for(int o=1;o<m;o++)
    cout<<mm[o]<<" ";
cout<<" ("<<ms<<")";
}

Fişier

7 6
1 2
1 5
1 6
2 3
2 6
6 7
6
7 5
1