Cod sursa(job #3203347)

Utilizator DomnulMilandruMilandru Nicon-David DomnulMilandru Data 13 februarie 2024 15:42:40
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb

#include <fstream>
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;
ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");
int n,m;
int x,y;
vector<vector<int>> A;
vector<int> grad;
stack<int> S;
unordered_map<long long,int> M;
void dfs(int nod)
{
    for(int i=0;i<A[nod].size();i++)
    {
        int vecin=A[nod][i];
        long long hash=0;
        if(vecin<nod)
          hash=vecin*100001+nod;
        else
          hash=nod*100001+vecin;
        if(M[hash])
        {
            M[hash]--;
            dfs(vecin);
        }
    }
    S.push(nod);
}
int main()
{
    cin>>n>>m;
    A.resize(n+1);
    grad.resize(n+1);
    for(int i=0;i<m;i++)
    {
        cin>>x>>y;
        A[x].push_back(y);
        A[y].push_back(x);
        grad[x]++;
        grad[y]++;
        long long hash=0;
        if(x<y)
          hash=x*100001+y;
        else
          hash=y*100001+x;
        M[hash]++;
    }
    for(int i=1;i<=n;i++)
      if(grad[i]%2==1 || !grad[i])
      {
          cout<<-1;
          return 0;
      }
    dfs(1);
    while(!S.empty())
    {
        if(S.size()>1)
        cout<<S.top()<<" ";
        S.pop();
    }
    return 0;
}