Probleme de informatica - enunturi si rezolvari

Se citeste un graf orientat cu n varfuri si m arce prin lista arcelor. Se citeste apoi un numar natural k mai mic decat n.
a) Afisati toate subgrafurile cu k varfuri ale subgrafului dat.
b) Afisati numarul maxim de arce ale unui subgraf cu k varfuri ale grafului dat.
c) Afisati cate dintre subgrafurile cu k varfuri ale subgrafului dat sunt complete.
Exemplu:
date.in
5 9
1 2
1 3
3 4
4 1
2 5
5 3
3 2
4 2
2 1
4
date.out
varfuri: 1 2 3 4
arce: (1,2) (1,3) (2,1) (3,2) (3,4) (4,1) (4,2)
varfuri: 1 2 3 5
arce: (1,2) (1,3) (2,1) (2,5) (3,2) (5,3)
varfuri: 1 2 4 5
arce: (1,2) (2,1) (2,5) (4,1) (4,2)
varfuri: 1 3 4 5
arce: (1,3) (3,4) (4,1) (5,3)
varfuri: 2 3 4 5
arce: (2,5) (3,2) (3,4) (4,2) (5,3)
maxim de arce: 7
numar de subgrafuri complete: 1

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int A[100][100], x[100],k,n,m,maxa=0,cc=0;

void citire()
{
    int i,j,p;
    fin>>n>>m;
    for(p=1;p<=m;p++)
    {
        fin>>i>>j;
        A[i][j]=1;
    }
    fin>>k;
}

void afis(int k)
{
    int i,j,c=0,ok=1;
    fout<<"varfuri: ";
    for(i=1;i<=k;i++) fout<<x[i]<<" ";
    fout<<endl<<"arce: ";
    for(i=1;i<=k;i++)
        for(j=1;j<=k;j++)
            if(A[x[i]][x[j]])
            {
                fout<<"("<<x[i]<<","<<x[j]<<") ";
                c++;
            }
    fout<<endl;
    if(c>maxa) maxa=c;
    for(i=1;i<=k;i++)
        for(j=i+1;j<=k;j++)
            if(A[x[i]][x[j]]+A[x[j]][x[i]]==0) ok=0;
    if(ok) cc++;
}

void back(int k, int pas)
{
    for(int i=x[pas-1]+1;i<=n;i++)
    {
        x[pas]=i;
        if(pas==k) afis(k);
        else back(k,pas+1);
    }
}

int main()
{
    citire();
    back(k,1);
    fout<<"maxim de arce: "<<maxa<<endl;
    fout<<"numar de subgrafuri complete: "<<cc;
    fin.close();
    fout.close();
    return 0;
}

26 apr 2024

Site-ul conține 884 de probleme rezolvate