Cod sursa(job #1027471)

Utilizator thesvcoolmanLucian Bicsi thesvcoolman Data 12 noiembrie 2013 20:03:40
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<fstream>
using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

int m,n,a[100][100],sol[100],d[100];
bool s[100];

void bfs(bool *s, int i)
{
    s[i]=1;
    int j;
    for(j=1;j<=n;j++)
        if(a[i][j] and !s[j])
            bfs(s,j);

}

bool isconex(int j)
{
    int i;
    for(i=1;i<=n;i++)
        s[i]=0;
    bfs(s,j);
    for(i=1;i<=n;i++)
        if(s[i]==0 and d[i])
            return false;
    return true;
}

void euler (int i)
{
    int j;
    for(j=1;j<=n;j++)
        if(a[i][j])
        {
            a[i][j]=a[j][i]=0;
            d[i]--;d[j]--;
            if(!isconex(j))
            {
                a[i][j]=a[j][i]=1;
                d[i]++;
                d[j]++;
            }
            else
            {
                sol[++sol[0]]=j;
                euler(j);
                return;
            }
        }
}
int main()
{
    fin>>n>>m;
    int i,x,y;
    for(i=1;i<=m;i++)
        fin>>x>>y,a[x][y]=a[y][x]=1,d[x]++,d[y]++;
    sol[0]=sol[1]=1;
    euler(1);
    for(i=1;i<=n;i++)
        if(d[i])
            {fout<<"-1";return 0;}
    for(i=1;i<=sol[0];i++)
        fout<<sol[i]<<" ";
    return 0;
}