Cod sursa(job #2084370)

Utilizator enedumitruene dumitru enedumitru Data 9 decembrie 2017 00:25:00
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
/// O(n^2)
#include <fstream>
#include <vector>
#include <list>
#define Nmax 100001
using namespace std;
ifstream f("ciclueuler.in"); ofstream g("ciclueuler.out");
vector <int> G[Nmax];
list <int> Q;
int N,M,viz[Nmax],gr[Nmax];
void euler(int x)
{   Q.push_back(x);
    while(!Q.empty())
    {   x=Q.front();
        if(G[x].empty()) {Q.pop_front(); g<<x<<' ';}
        else
        {   int i=G[x].back(); G[x].pop_back();
            Q.push_front(i);
            vector<int>::iterator it=G[i].begin(),sf=G[i].end();
            for(;it!=sf;++it)
                if(*it==x) {G[i].erase(it); break;}
        }
    }
}
void dfs(int nod)
{   viz[nod]=true;
    for(unsigned int i=0;i<G[nod].size();++i)
        if(!viz[G[nod][i]]) dfs(G[nod][i]);
}
int main()
{   f>>N>>M;
    for(int x,y,i=1;i<=M;i++)
    {   f>>x>>y; gr[x]++; gr[y]++;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1);
    for(int i=1;i<=N;++i)
        if(!viz[i]) {g<<-1; return 0;}
    for(int i=1;i<=N;++i)
        if(gr[i]%2) {g<<-1; return 0;}
    euler(1);
    return 0;
}