Cod sursa(job #1343107)

Utilizator dumitrualexAlex Dumitru dumitrualex Data 14 februarie 2015 21:38:28
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <vector>
#include <stack>
#define add push_back
#define nmax 100000+5
using namespace std;

vector<int> graf[nmax];
stack<int> s;
vector<int> solutie;
int n, m;

int search(vector<int> v, int x)
{
    int i;
    for (i = 0; i < v.size(); i++)
        if (v[i] == x)
            return i;
    return -1;
}

int main()
{
    freopen("ciclueuler.in", "r", stdin);
    freopen("ciclueuler.out", "w", stdout);

    int i, j, indx;
    int a, b, p, v;
    int muchii_vizitate;
    scanf("%d%d", &n, &m);

    for (i = 0; i < m; i++)
    {
        scanf("%d%d", &a, &b);
        graf[a].add(b);
        graf[b].add(a);
    }

    muchii_vizitate = 0;
    s.push(1);
    while (!s.empty())
    {
        p = s.top();
        if (!graf[p].empty())
        {
            v = graf[p][0];
            indx = search(graf[v], p);

            graf[p].erase(graf[p].begin());
            if (indx != -1)
                graf[v].erase(graf[v].begin()+indx);

            muchii_vizitate++;
            s.push(v);
            continue;
        }

        solutie.add(p);
        s.pop();
    }

    if (muchii_vizitate == m)
    {
        for (i = 0; i < solutie.size(); i++)
            printf("%d ", solutie[i]);
    }
    else
        printf("%d", -1);
    return 0;
}