Un graf orientat se numește graf turneu dacă oricare ar fi două noduri diferite i, j, între ele există un singur arc: arcul (i j) sau arcul (j i). În orice graf turneu există un drum elementar care trece prin toate nodurile grafului.

Cerința

Se dă un graf turneu cu n noduri. Să se determine un drum elementar care să conțină toate nodurile grafului.

Date de intrare

Programul citește de la tastatură numărul de noduri n, iar apoi n*(n-1)/2 perechi i j, cu semnificația că există arcul (i j).

Date de ieșire

Programul va afișa pe ecran cele n noduri ale drumului determinat, separate prin exact un spațiu.

Restricții și precizări

1 ≤ n ≤ 100
orice drum corect determinat este acceptat

Exemplu

Intrare

Ieșire

1 4 3 2

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 Turneu:

#include <iostream>
#include <fstream>
using namespace std;

int n , a[105][105], x[105];

int main()
{
    int i , j , m;
    cin >> n;
    m = n * (n - 1) / 2;
    while( m )
    {
        cin >> i >> j;
        a[i][j] = 1;
        m --;
    }
    m = 2;
    if(a[1][2] == 1)
        x[1] = 1, x[2] = 2;
    else
        x[1] = 2, x[2] = 1;
    for(int i = 3 ; i <= n ; ++i)
    {
        int p = 0;
        if(a[x[m]][i] == 1)
            p = m + 1;
        else
            if(a[i][x[1]] == 1)
                p = 1;
            else
                for(int j = 1 ; j < m && p == 0 ; ++j)
                    if(a[x[j]][i] == 1 && a[i][x[j+1]] == 1)
                        p = j + 1;
        for(int j = m ; j >= p ; --j)
            x[j+1] = x[j];
        x[p] = i;
        m ++;
    }
    for(int i = 1; i <= n ; ++i)
        cout << x[i] << " ";
    cout << "
";
    return 0;
}

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 #582 Turneu

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #582 Turneu 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 #582 Turneu