Cod sursa(job #2462642)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 27 septembrie 2019 18:06:04
Problema Ciclu Eulerian Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
#include <vector>
using namespace std;
vector <int> G[205];
struct muchii
{
    int u , v;
};
muchii edge[500005];
int ans[500005] , viz[500005] , d[100005] , m;
void euler(int u)
{
    int j , v , ind;
    ans[++ ans[0]] = u;
    for(j = 0 ; j < G[u].size() ; j ++)
    {
        ind = G[u][j];
        v = edge[ind].v;
        if(edge[ind].v == u)
            v = edge[ind].u;
        if(!viz[G[u][j]] && (ans[0] == m || d[v] - 1 > 0))
        {
            viz[ind] = 1;
            d[u] --;
            d[v] --;
            euler(v);
        }
    }
}
int main()
{
    freopen("ciclueuler.in" , "r" , stdin);
    freopen("ciclueuler.out" , "w" , stdout);
    int n , i , u , v;
    scanf("%d%d" , &n , &m);
    for(i = 1 ; i <= m ; i ++)
    {
        scanf("%d%d" , &u , &v);
        G[u].push_back(i);
        G[v].push_back(i);
        edge[i].u = u;
        edge[i].v = v;
        d[u] ++;
        d[v] ++;
    }
    euler(1);
    if(ans[0] == m + 1)
    {
        for(i = 1 ; i < ans[0] ; i ++)
            printf("%d " , ans[i]);
    }
    else
        printf("-1\n");
    return 0;
}