Cod sursa(job #1621794)

Utilizator mariapascuMaria Pascu mariapascu Data 29 februarie 2016 21:46:25
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.01 kb
#include <fstream>
#include <queue>
#include <vector>
#include <stack>
#include <list>
using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

const int DIM = 100004;
int n, m;
list<int> G[DIM], L;
vector<int> grd;
vector<bool> s;
stack<int> S;

void Read();
void Write(int x);
int Result();
int Eulerian();
void BFS(int x);

int main() {
    Read();
    Write(Result());
    fin.close();
    fout.close();
    return 0;
}

void BFS(int x) {
    queue<int> Q;
    s[x] = true;
    Q.push(x);
    while (!Q.empty()) {
        x = Q.front(); Q.pop();
        for (list<int> :: iterator it = G[x].begin(); it != G[x].end(); ++it)
        if (!s[*it]) {
            s[*it] = true;
            Q.push(*it);
        }
    }
}


int Eulerian() {
    for (int i = 1; i <= n; i++)
        if (grd[i] % 2 == 1) return 0;
    BFS(1);
    for (int i = 1; i <= n; i++)
        if (s[i] == false) return 0;
    return 1;
}

void Erase(int v, int w) {
    grd[v]--, grd[w]--;
    G[v].pop_front();
    for (list<int> :: iterator it = G[w].begin(); it != G[w].end(); ++it)
        if (*it == v){
            G[w].erase(it);
            break;
        }
}

void Euler(int v) {
    while (true) {
        if (G[v].empty()) break;
        int w = G[v].front();
        S.push(v);
        Erase(v, w);
        v = w;
    }
}

int Result() {
    int v = Eulerian();
    if (v == 0) return -1;
    do {
        Euler(v);
        v = S.top(); S.pop();
        L.push_back(v);
    } while (!S.empty());
    return 1;
}

void Write(int x) {
    if (x == -1) fout << "-1";
    else {
        for (list<int> :: iterator it = L.begin(); it != L.end(); ++it)
            fout << *it << ' ';
    }
}

void Read() {
    fin >> n >> m;
    grd = vector<int>(n + 1, 0);
    s = vector<bool>(n + 1, false);
    for (int i = 1, x, y; i <= m; i++) {
        fin >> x >> y;
        G[x].push_back(y); grd[x]++;
        G[y].push_back(x); grd[y]++;
    }
}