Cod sursa(job #1998956)

Utilizator dadadadadada da dadadada Data 9 iulie 2017 19:35:20
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <fstream>
using namespace std;
ifstream fin("euler.in");
ofstream fout("euler.out");
int n,m,A[300][300],P[300],k,G[300],sol[12000],cnt;

void citire()
{
    int x,y;
    fin>>n;
    while (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;
    sol[++cnt] = 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())
    {
        ciclu_eulerian(1);
    }

    fin.close();
    fout << cnt << endl;
    for ( int i = 1 ; i <= cnt ; i ++ )
        fout << sol[i] << " ";
    fout.close();
    return 0;
}