Cod sursa(job #1349330)

Utilizator diana97Diana Ghinea diana97 Data 20 februarie 2015 09:43:16
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.09 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

ifstream f ("domino.in");
ofstream g ("domino.out");

const int NMAX = 50000 + 1;

int n, start;
bool vizitat[NMAX];
vector <int> v[10], nr[10];
vector <bool> intors[10];
stack <int> stiva;

void citeste() {
    f >> n;
    int a, b;

    for (int i = 1; i <= n; i++) {
        f >> a >> b;
        v[a].push_back(b);
        intors[a].push_back(false);
        nr[a].push_back(i);
        v[b].push_back(a);
        intors[b].push_back(true);
        nr[b].push_back(i);
    }
}


void euler(int nod) {
    stiva.push(nod);
    int fiu, l;
    while (!stiva.empty()) {
        nod = stiva.top();
        l = v[nod].size();
        if (l == 0) {
            //g << nod << ' ';
            stiva.pop();
        }
        else {
            fiu = v[nod][l - 1];
            g << nr[nod][l - 1] << ' ' << intors[nod][l - 1] << '\n';
            stiva.push(fiu);
            v[fiu].erase(find(v[fiu].begin(), v[fiu].end(), nod));
            nr[fiu].erase(find(nr[fiu].begin(), nr[fiu].end(), nr[nod][l - 1]));
            intors[fiu].erase(find(intors[fiu].begin(), intors[fiu].end(), intors[nod][l - 1]));
            v[nod].pop_back();
            nr[nod].pop_back();
            intors[nod].pop_back();
        }
    }
}


void DFS(int nod) {
    vizitat[nod] = true;
    int l = v[nod].size(), fiu;
    for (int i = 0; i < l; i++) {
        fiu = v[nod][i];
        if (vizitat[fiu]) continue;
        DFS(fiu);
    }
}

bool verifica() {
    int nr_impar = 0;
    for (int i = 0; i <= 9; i++)
        if (v[i].size() % 2 == 1) nr_impar++;
    if (nr_impar != 0 && nr_impar != 2) return false;
    for (int i = 0; i <= 9; i++)
        if (v[i].size()) {
            start = i;
            break;
        }
    DFS(start);
    for (int i = start + 1; i <= 9; i++)
        if (v[i].size() && !vizitat[i]) return false;
    return true;
}

int main() {
    bool ok;
    citeste();
    ok = verifica();
    if (!ok) {g << "0\n"; return 0;}
    for (int i = 1; i <= n; i++) vizitat[i] = false;
    g << "1\n";
    euler(1);
}