Cod sursa(job #1979444)

Utilizator refugiatBoni Daniel Stefan refugiat Data 10 mai 2017 17:03:19
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1 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];

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";return 0;}

    DFS(1);
    for(int i = 1; i < K; i++)
        fout << q[i] << " ";
    fout << "\n";

    fout.close();
    return 0;
}