Cod sursa(job #3374996)

Utilizator Razvan0wVoicu Razvan Razvan0w Data 9 noiembrie 2026 22:07:41
Problema Sate Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <fstream>
using namespace std;

ifstream fisier_intrare("drumuri.in");
ofstream fisier_iesire("drumuri.out");

int primul[10001];
int urmator[60001];
int destinatie[60001];
int numar_drum[60001];
bool vizitat[10001];
bool drum_marcat[30001];
int paznici[15001][3];
int nr_paznici;

bool parcurgere(int nod, int nod_parinte)
{
    vizitat[nod] = true;
    int in_asteptare = 0;

    for (int p = primul[nod]; p != 0; p = urmator[p]) {
        int vecin = destinatie[p];
        int id = numar_drum[p];

        if (drum_marcat[id])
            continue;
        drum_marcat[id] = true;

        bool liber = true;
        if (!vizitat[vecin])
            liber = !parcurgere(vecin, nod);

        if (liber) {
            if (in_asteptare == 0)
                in_asteptare = vecin;
            else {
                paznici[nr_paznici][0] = in_asteptare;
                paznici[nr_paznici][1] = nod;
                paznici[nr_paznici][2] = vecin;
                nr_paznici++;
                in_asteptare = 0;
            }
        }
    }

    if (in_asteptare != 0 && nod_parinte != 0) {
        paznici[nr_paznici][0] = in_asteptare;
        paznici[nr_paznici][1] = nod;
        paznici[nr_paznici][2] = nod_parinte;
        nr_paznici++;
        return true;
    }

    return false;
}

int main()
{
    int nr_orase, nr_drumuri;
    fisier_intrare >> nr_orase >> nr_drumuri;

    int contor = 0;
    for (int i = 1; i <= nr_drumuri; i++) {
        int oras_a, oras_b;
        fisier_intrare >> oras_a >> oras_b;

        contor++;
        destinatie[contor] = oras_b;
        numar_drum[contor] = i;
        urmator[contor] = primul[oras_a];
        primul[oras_a] = contor;

        contor++;
        destinatie[contor] = oras_a;
        numar_drum[contor] = i;
        urmator[contor] = primul[oras_b];
        primul[oras_b] = contor;
    }

    if (nr_drumuri % 2 == 1) {
        fisier_iesire << 0 << "\n";
        return 0;
    }

    parcurgere(1, 0);

    fisier_iesire << 1 << "\n";
    for (int i = 0; i < nr_paznici; i++)
        fisier_iesire << paznici[i][0] << " " << paznici[i][1] << " " << paznici[i][2] << "\n";
}