Cod sursa(job #2105059)

Utilizator AlexVulpoiuAlexandru Vulpoiu AlexVulpoiu Data 12 ianuarie 2018 16:10:18
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
vector <pair<int,int> > a[100001];
stack <int> stiva;
int n,m,i,j,k;
bool grad[100001],v[500001];
int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for(k=1;k<=m;k++)
    {
        scanf("%d %d\n",&i,&j);
        a[i].push_back(make_pair(j,k));
        a[j].push_back(make_pair(i,k));
        grad[i]=1-grad[i];
        grad[j]=1-grad[j];
    }
    for(i=1;i<=n;i++)
        if(grad[i])
        {
            printf("-1\n");
            return 0;
        }
    n=0;
    stiva.push(1);
    while(!stiva.empty())
    {
        i=stiva.top();
        if(a[i].size())
        {
            j=a[i].back().first;
            k=a[i].back().second;
            a[i].pop_back();
            if(!v[k])
            {
                v[k]=1;
                stiva.push(j);
            }
        }
        else
        {
            stiva.pop();
            if(++n<=m)
                printf("%d ",i);
        }
    }
    printf("\n");
    return 0;
}