Cod sursa(job #2841860)

Utilizator Matei_PanzariuMatei Panzariu Matei_Panzariu Data 30 ianuarie 2022 16:13:35
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");
vector<int>ans;
vector<vector<pair<int,int>> >mu;
stack<int>st;
int n,m,muchii[500002],unde[500002];
void DF(int nod)
{
    for(int i=unde[nod];i<mu[nod].size();i++)
    {
        int nxt=mu[nod][i].first;
        int much=mu[nod][i].second;
        if(muchii[much]==0)
        {
            unde[nod]=i+1;
            muchii[much]=1;
            st.push(nxt);
            nod=nxt;
            i=unde[nod]-1;
        }
    }
}
int main()
{
    cin>>n>>m;
    mu.resize(n+1);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        mu[x].emplace_back(make_pair(y,i));
        mu[y].emplace_back(make_pair(x,i));
    }
    for(int i=1;i<=n;i++)
    {
        if(mu[i].size()==0 || mu[i].size()%2==1)
        {
            cout<<-1;
            return 0;
        }
    }
    st.push(1);
    while(st.empty()==0)
    {
        int x=st.top();
        DF(x);
        ans.emplace_back(st.top());
        st.pop();
    }
    for(int i=ans.size()-1;i>=0;i--)
        cout<<ans[i]<<' ';
}