Fie G un graf neorientat cu 2 * N noduri și 3 * N - 2 muchii. Fiecare muchie este colorată în alb, negru sau roșu.
Se garantează următoarele:

Există N-1 muchii albe. Capetele lor sunt noduri din mulțimea 1, 2, ..., N. Ele formează un arbore.
Există N-1 muchii negre. Capetele lor sunt noduri din mulțimea N+1, N+2, ..., 2*N. Ele formează un arbore.
Există N muchii roșii. Fiecare muchie are un capăt în mulțimea 1, 2, ..., N și celălalt capăt în mulțimea N+1, N+2, ..., 2*N.

Cele 2 * N capete ale muchiilor roșii sunt distincte două câte două. Cu alte cuvinte, fiecare nod din graf are exact o muchie roșie incidentă.
Numim ciclu hamiltonian special un ciclu care:

vizitează fiecare nod al grafului exact o dată.
nu parcurge consecutiv două muchii de aceeași culoare.
începe din nodul 1, iar prima muchie parcursă este de culoare roșie.

Cerința

Afișați un ciclu hamiltonian special al grafului G sau constatați că nu există niciun astfel de ciclu.

Date de intrare

Fișierul de intrare dungeon.in va conține pe prima linie un număr natural T reprezentând numărul de teste. Pentru fiecare test pe prima linie se află valoarea N. Pe următoarele N-1 linii se găsesc perechi de valori reprezentând capetele muchiilor de culoare albă (valori de la 1 la N). Următoarele N-1 linii conţin perechi de valori ce reprezintă capetele muchiilor de culoare neagră (valori de la N+1 la 2*N). Următoarele N perechi de valori reprezintă capetele muchiilor de culoare roşie.

Date de ieșire

Fișierul de ieșire dungeon.out va conține pentru fiecare din cele T teste câte o linie cu 2*N valori reprezentând succesiunea nodurilor care formează ciclul hamiltonian special al fiecărui graf dat, respectiv valoarea -1 dacă nu există un astfel de ciclu.

Restricții și precizări

N ≤ 50 000
T ≤ 5
Pentru teste in valoare de 20 puncte se garantează că N ≤ 10
Pentru alte teste in valoare de 30 puncte se garantează că ambii arbori au forma de lanţ.

Exemplu

dungeon.in

dungeon.out

-1
1 7 6 4 3 5 8 2

Explicație

Există două teste. În fiecare test graful are 2*4 noduri şi 3*4-2 muchii (3 muchii de culoare albă, 3 muchii de culoare neagră, respectiv 4 muchii de culoare roşie). În primul graf nu se găseşte un ciclu hamiltonian special.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema dungeon:

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <queue>

using namespace std;

void dfs(int node, const vector< vector<int> > &edges, vector<bool>& used) {
    if (used[node])
        return;
    used[node] = true;
    for (auto &x : edges[node])
        dfs(x, edges, used);
}

int main() {
    ifstream cin("dungeon.in");
    ofstream cout("dungeon.out");

    int T; cin >> T;
    assert(1 <= T && T <= 5);
    while (T--) {
        int N; assert(cin >> N);
        assert(1 <= N && N <= 50000);
        vector< vector<int> > edges(2 * N);
        for (int i = 0; i < N - 1; ++i) {
            int x, y; assert(cin >> x >> y);
            assert(1 <= x && x <= N);
            assert(1 <= y && y <= N);
            assert(x != y);
            edges[x - 1].push_back(y - 1);
            edges[y - 1].push_back(x - 1);
        }

        for (int i = 0; i < N - 1; ++i) {
            int x, y; assert(cin >> x >> y);
            assert(N + 1 <= x && x <= N * 2);
            assert(N + 1 <= y && y <= N * 2);
            assert(x != y);
            edges[x - 1].push_back(y - 1);
            edges[y - 1].push_back(x - 1);
        }

        vector<bool> matched(2 * N, false);
        vector< vector<int> > matching(2 * N);

        for (int i = 0; i < N; ++i) {
            int x, y; assert(cin >> x >> y);
            if (x > y)
                swap(x, y);
            assert(1 <= x && x <= N);
            assert(N + 1 <= y && y <= 2 * N);
            --x; --y;
            matched[x] = true;
            matched[y] = true;
            matching[x].push_back(y);
            matching[y].push_back(x);
        }

        assert(matched == vector<bool>(2 * N, true));
        vector<bool> used(2 * N, false);
        dfs(0, edges, used);
        dfs(N, edges, used);
        assert(used == vector<bool>(2 * N, true));

        queue<int> Q;
        vector<int> degree(2 * N, 0);
        for (int i = 0; i < 2 * N; ++i) {
            degree[i] = edges[i].size();
            if (degree[i] == 1)
                Q.push(i);
        }

        while (!Q.empty()) {
            int node = Q.front();
            Q.pop();
            for (auto &x : edges[node]) {
                if (degree[x] > 0) {
                    matching[x].push_back(node);
                    matching[node].push_back(x);
                    degree[node] = 0;
                    degree[x] = 0;
                    for (auto &y : edges[x]) {
                        if (--degree[y] == 1)
                            Q.push(y);
                    }
                }
            }
        }

        bool ok = true;
        for (int i = 0; i < 2 * N; ++i)
            if (matching[i].size() != 2) {
                ok = false;
            }
        if (!ok) {
            cout << "-1\n";
            continue;
        }

        vector<int> answer;
        int node = 0;
        int last = -1;
        do {
            answer.push_back(node);
            for (int i = 0; i < 2; ++i)
                if (matching[node][i] != last) {
                    int next = matching[node][i];
                    last = node;
                    node = next;
                    break;
                }
        } while (node);
        if (int(answer.size()) != 2 * N) {
            cout << "-1\n";
            continue;
        }

        for (auto &x : answer)
            cout << x + 1 << " ";
        cout << "\n";
    }
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2469 dungeon

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2469 dungeon de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2469 dungeon