Cod sursa(job #1979440)

Utilizator refugiatBoni Daniel Stefan refugiat Data 10 mai 2017 16:59:46
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
#define nmax 500005
using namespace std;
int st[nmax], dr[nmax], q[nmax];
int poz[nmax];
/// poz[i] - pozitia unde am ramas in lista de adiacenta L[i]
int N, M, K;
bitset <nmax> viz ;
vector <int> L[100005];



inline void DFS(int nod)
{
    while (poz[nod] < L[nod].size())
    {
        int k = L[nod][poz[nod]++];
        if(!viz[k])
        {
            viz[k] = 1;
            DFS(st[k] + dr[k] - nod);
        }
    }
    q[++K] = nod;
}



int main()
{

    ifstream fin("ciclueuler.in");
    fin >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        fin >> st[i] >> dr[i];
        L[st[i]].push_back(i);
        L[dr[i]].push_back(i);
    }
    bool ok=true;

    for(int i = 1; i <= N; i++)
        if(L[i].size() % 2 == 1) ok=false;


    ofstream fout("ciclueuler.out");
    if(!ok) fout << "-1\n";
    else
    {
        DFS(1);
        for(int i = 1; i < K; i++)
            fout << q[i] << " ";
        fout << "\n";
    }
    fout.close();
    return 0;
}