Probleme de informatică
  Clasa a IX-a
1. Elementele de bază ale limbajului C++ (instructiunile limbajului) (46)
2. Subprograme predefinite (1)
3. Tablouri (145)
4. Fişiere text (2)
5. Algoritmi elementari (106)
6. Probleme diverse (13)
  Clasa a X-a
1. Subprograme definite de utilizator (87)
2. Şiruri de caractere (47)
3. Înregistrări (26)
4. Recursivitate (57)
5. Combinatorica (0)
6. Alocarea dinamică a memoriei (2)
7. Liste înlănţuite (25)
8. Algoritmul lui Lee (1)
  Clasa a XI-a

1. Metoda "Divide et impera" (12)
2. Metoda Backtracking (85)
3. Metoda Greedy (6)
4. Programare dinamică (18)
5. Grafuri neorientate (37)
6. Grafuri orientate (38)
7. Arbori (33)

  Clasa a XII-a
1. Elemente de baza C# (32)
2. POO in C# (13)
3. C# - Windows Form Application (24)
4. Admitere UBB (18)

   Home Grafuri neorientate Bacalaureat 2016   |   Variante bacalaureat 2009   |   Atestat  |   Olimpiada       
Noutăţi
Subiecte admitere la Facultatea de informatica UBB Cluj-Napoca
Subiecte bacalaureat 2010-2018
Bacalaureat 2018 - competenţe digitale
C# - Windows Form Application - exemple
Modele de proiecte de atestat
Bacalaureat 2018
Subiecte si rezolvări 2010-2018
Rezolvari variante bacalaureat 2009
Competenţe digitale
Examen atestat
Rezumat documentatie
php.doc
css.doc
exemple_php_si_css.rar
Modele de proiecte de atestat
Olimpiada
Clasele V-VI
Clasele VII-VIII
Clasa a IX-a
Clasa a X-a
Clasele XI-XII
Noţiuni teoretice
Metode de sortare
Metoda backtracking


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;
}


  Clasa a IX-a
1. Elementele de bază ale limbajului C++ (instructiunile limbajului) (46)
2. Subprograme predefinite (1)
3. Tablouri (145)
4. Fişiere text (2)
5. Algoritmi elementari (106)
6. Probleme diverse (13)
  Clasa a X-a
1. Subprograme definite de utilizator (87)
2. Şiruri de caractere (47)
3. Înregistrări (26)
4. Recursivitate (57)
5. Combinatorica (0)
6. Alocarea dinamică a memoriei (2)
7. Liste înlănţuite (25)
8. Algoritmul lui Lee (1)
  Clasa a XI-a

1. Metoda "Divide et impera" (12)
2. Metoda Backtracking (85)
3. Metoda Greedy (6)
4. Programare dinamică (18)
5. Grafuri neorientate (37)
6. Grafuri orientate (38)
7. Arbori (33)

  Clasa a XII-a
1. Elemente de baza C# (32)
2. POO in C# (13)
3. C# - Windows Form Application (24)
4. Admitere UBB (18)

Calculatoare si accesorii second hand
Copyright 2009-2017 Muresan Vasile Ciprian - mcip.ro