Cod sursa(job #2087938)

Utilizator mariastStoichitescu Maria mariast Data 14 decembrie 2017 16:17:59
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<cstdio>
#include<stack>
#include<queue>
using namespace std;
stack<int> q;
vector<int>g[100010];
int n,m,x,y,u,v,i,j,nr;

int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        if(g[i].size()%2==1){
            printf("-1");
            return 0;
        }
    q.push(1);
    while(!q.empty()){
        x=q.top();
        if(g[x].size()==0){
            q.pop();
            nr++;
            if(nr<=m){
                printf("%d ",x);
            }
        }
        else{
            u=g[x][0];
            q.push(u);
            g[x].erase(g[x].begin()+0);
            for(i=0;i<g[u].size();i++)
                if(g[u][i]==x) {
                    g[u].erase(g[u].begin()+i);
                    break;
                }

        }
    }
}