Pagini recente » Cod sursa (job #2696797) | Cod sursa (job #2639806) | Cod sursa (job #2919273) | Cod sursa (job #379758) | Cod sursa (job #1349329)
#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);
}