Probleme de informatică
Clasa a IX-a
Elementele de bază C++ (46)
Subprograme predefinite (1)
Fişiere text (2)
Algoritmi elementari (111)
Tablouri unidimensionale (83)
Tablouri bidimensionale (64)
Probleme diverse (13)
Clasa a X-a
Subprograme (funcții) (87)
Şiruri de caractere (50)
Tipul înregistrare (26)
Recursivitate (57)
Alocarea dinamică a memoriei (2)
Liste înlănţuite (25)
Algoritmul lui Lee (1)
Clasa a XI-a
Metoda "Divide et impera" (12)
Metoda Backtracking (86)
Metoda Greedy (6)
Programare dinamică (18)
Grafuri neorientate (40)
Grafuri orientate (38)
Arbori (33)
Clasa a XII-a
Elemente de bază C# (32)
POO în C# (14)
Programare vizuală în C# (19)
Examen de bacalaureat
Competențe digitale
Examen de atestat
Admitere UBB (18)
Se dau două grafuri neorientate G1 și G2 cu n (n<=100) vârfuri și m1, respectiv m2 muchii prin listele muchiilor, în două fișiere graf1.in, respectiv graf2.in. Verificați dacă unul dintre ele este graf parțial al celuilalt. Se va preciza dacă G1 este graf parțial al lui G2, dacă G2 este graf parțial al lui G1 sau NU dacă niciunul dintre ele este graf parțial al celuilalt.
Exemplu:
graf1.in
5 2
1 4
1 3
graf2.in
5 5
1 4
1 3
3 5
4 5
2 5
graf.out
G1 este graf partial al lui G2

#include <fstream>
using namespace std;
ifstream fin1("graf1.in");
ifstream fin2("graf2.in");
ofstream fout("graf.out");

int n,m1,m2,A[101][101],B[101][101],x,y;

int graf_partial(int n, int A[][101], int B[][101])
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(B[i][j]==1 && A[i][j]==0) return 0;
    return 1;
}

int main()
{
    fin1>>n>>m1;
    for(int i=1;i<=m1;i++)
    {
        fin1>>x>>y;
        A[x][y]=A[y][x]=1;
    }
    fin2>>n>>m2;
    for(int i=1;i<=m2;i++)
    {
        fin2>>x>>y;
        B[x][y]=B[y][x]=1;
    }
    if(m1>m2)
        if(graf_partial(n,A,B)) fout<<"G2 este graf partial al lui G1";
        else fout<<"NU";
    else
        if(graf_partial(n,B,A)) fout<<"G1 este graf partial al lui G2";
        else fout<<"NU";
    return 0;
}

03 nov 2024
Site-ul conține 884 de probleme rezolvate
Copyright © 2009-2018 Muresan Vasile Ciprian