Salut! Am intalnit problema asta dar nu am gasit solutia niciunde.
Competitie dificila
La o competitie au participat N concurenti. Fiecare dintre ei a primit un numar de concurs astfel încât sa nu existe concurenti cu acelasi numar. Numerele de concurs apartin multimii {1,2,...,N}. Din pacate, clasamentul final a fost pierdut, iar comisia îsi poate aduce aminte doar câteva relatii între unii participanti (de genul "participantul cu numarul 3 a iesit înaintea celui cu numarul 5").
Cerinta
Seful comisiei are nevoie de un clasament final si va cere sa-l ajutati determinând primul clasament în ordine lexicografica ce respecta relatiile pe care si le aminteste comisia.
Date de intrare
Fisier de intrare: COMPET.IN
Linia 1: N M
· doua numere naturale nenule, reprezentând numarul concurentilor, respectiv numarul relatiilor pe care si le aminteste comisia;
Liniile 2..M+1: i j
· pe fiecare din aceste M linii se afla cate doua numere naturale nenule i si j, având semnificatia: concurentul cu numarul de concurs i a fost în clasament înaintea concurentului cu numarul de concurs j.
Date de iesire
Fisier de iesire: COMPET.OUT
Linia 1: nr1 nr2 ... nrN
· pe aceasta linie se va scrie clasamentul sub forma unui sir de numere naturale nenule, separate prin câte un spatiu, reprezentând numerele de concurs ale concurentilor, în ordine de la primul clasat la ultimul..
Restrictii si precizari
· 1< N <= 1000
· se garanteaza corectitudinea datelor de intrare si faptul ca exista totdeauna o solutie.
Exemplul 1
COMPET.IN
3 1
1 2
COMPET.OUT
1 2 3
Exemplul 2
COMPET.IN
4 2
2 1
3 4
COMPET.OUT
2 1 3 4
Timp maxim de executare/test: 1 secunda
Am o matrice in care pe linia i am indicii participantilor care sunt in fata lui i. v[ i ][ 0 ]=numarul lor. Apoi, am un vector v2, v2[ i ]=cati sunt in fata lui i. De aici nu mai stiu ce sa fac. Am incercat sa afisez in paralel doi vectori (Un vector sortat crescator in functie de numarul de elemente din fata lui i, si un vector care contine elementele despre care nu stim nimic.) Problema e ca (pentru al 2-lea test, de exemplu) 1 are un element in fata lui iau 2 nu are pe nimeni inaintea lui iar eu obtin 2 3 1 4 nu 2 1 3 4. Imi puteti explica ce trebuie facut?
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena