Cod sursa(job #2031276)

Utilizator mihai.alphamihai craciun mihai.alpha Data 2 octombrie 2017 22:32:17
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <vector>
#include <stack>

FILE *fin, *fout;

#define MAXN (int)1e5
#define MAXM (int)5e5

int N, M;
int to[MAXM + 1], from[MAXM + 1];
std::vector<int> v[MAXN + 1];
int sol[MAXM + 2];
std::stack <int> st;
bool viz[MAXM + 1];

int main()  {
    fin = fopen("ciclueuler.in", "r");
    fout = fopen("ciclueuler.out", "w");
    fscanf(fin, "%d%d", &N, &M);
    for(int i = 1;i <= M;i++)  {
        fscanf(fin, "%d%d", &to[i], &from[i]);
        v[to[i]].push_back(i);
        v[from[i]].push_back(i);
    }
    for(int i = 1;i <= N;i++)  {
        if(v[i].size() & 1)  {
            fprintf(fout, "-1");
            return 0;
        }
    }
    st.push(1);
    while(!st.empty())  {
        int a = st.top();
        if(v[a].size())  {
            int much = v[a].back();
            v[a].pop_back();
            if(viz[much] == 0)  {
                viz[much] = 1;
                st.push(a ^ to[much] ^ from[much]);
            }
        }
        else  {
            st.pop();
            sol[++sol[0]] = a;
        }
    }
    for(int i = 1;i < sol[0];i++)
        fprintf(fout, "%d ", sol[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}