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 sa un graf neorientat cu n varfuri si m muchii, fara varfuri izolate.
Sa se determine daca este eulerian si in caz afirmativ sa se afiseze un ciclu eulerian.
Pentru determinarea ciclului eulerian nu se va folosi metoda backtracking.
date.in:
6 10
1 2
1 6
2 3
2 5
2 6
3 4
3 5
3 6
4 5
5 6
date.out:
este eulerian
1 2 3 5 6 2 5 4 3 6 1

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

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

int grad(int k)//calculeaza gradul varfului k
{
    int s=0;
    for(int i=1;i<=n;i++)
        if(A[k][i]==1) s++;
    return s;
}

void DF(int s)//parcurge graful din varful s si marcheaza varfurile accesibile
{
    P[s]=1;
    for(int i=1;i<=n;i++)
        if(A[s][i]==1 && P[i]==0)
            DF(i);
}

int conex()//conexitatea grafului
{
    DF(1);
    for(int i=1;i<=n;i++)
        if(P[i]==0) return 0;
    return 1;
}

int euler()//daca este eulerian
{
    if(!conex()) return 0;//conex
    for(int i=1;i<=n;i++)
        if(G[i]%2==1) return 0;//si toate gradele pare
    return 1;
}

void ciclu_eulerian(int k)//construieste un ciclu eulerian
{
    int maxx=0,nmax=0;
    fout<<k<<" "; //afiseaza varful curent
    for(int i=1;i<=n;i++)//cauta varful urmator cu grad maxim
    {
        if(A[k][i]==1)
            if(G[i]>maxx)
            {
                maxx=grad(i);
                nmax=i;
            }
    }
    if(nmax!=0)
        {   A[k][nmax]=A[nmax][k]=0;//sterge mughia
            G[k]--;//scade gradele
            G[nmax]--;
            ciclu_eulerian(nmax);//merge in varful urmator
        }
}

int main()
{
    citire();
    for(int i=1;i<=n;i++) G[i]=grad(i);
    if(euler())
    {
        fout<<"este eulerian\n";
        ciclu_eulerian(1);
    }
    else fout<<"nu este eulerian\n";

    fin.close();
    fout.close();
    return 0;
}

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