Cod sursa(job #1171142)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 15 aprilie 2014 11:54:03
Problema Ciclu Eulerian Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

int n,m,i,x,y,nr,grad[100005];

bitset<500005> ok;

vector< pair<int,int> > l[100005];

void dfs(int nod) {
    ok[nod]=1;
    for(int i=0;i<l[nod].size();i++) {
        nr++;
        if(ok[l[nod][i].first]==0) {
            dfs(l[nod][i].first);
        }
    }
}

void euler(int nod) {
    for(i=l[nod].size()-1;i>=0;i--) {
        pair<int,int> x=l[nod][i];
        if(ok[x.second]==0) {
            ok[x.second]=1;
            euler(x.first);
        }
        l[nod].pop_back();
    }
    g<<nod<<" ";
}

int main() {
    f>>n>>m;
    for(i=1;i<=m;i++) {
        f>>x>>y;
        grad[x]++;
        grad[y]++;
        l[x].push_back(make_pair(y,i));
        l[y].push_back(make_pair(x,i));
    }
    for(i=1;i<=n;i++)
        if(grad[i]%2==1) {
            g<<"-1\n";
            return 0;
        }
    dfs(1);
    for(i=1;i<=m;i++)
        ok[i]=0;
    if(nr!=2*m) {
        g<<"-1\n";
        return 0;
    }
    euler(1);
    return 0;
}