La o competiție au participat N concurenți. Fiecare dintre ei a primit un număr de concurs astfel încât să nu existe concurenți cu același număr. Numerele de concurs aparțin mulțimii {1,2,...,N}. Din păcate, clasamentul final a fost pierdut, iar comisia își poate aduce aminte doar câteva relații între unii participanți (de genul “participantul cu numărul 3 a ieșit înaintea celui cu numărul 5”).
Cerința
Șeful comisiei are nevoie de un clasament final și vă cere să-l ajutați determinând primul clasament în ordine lexicografică ce respectă relațiile pe care și le amintește comisia.
Date de intrare
Fișierul de intrare competitie.in conține pe prima linie doua numere naturale nenule N și M, reprezentând numărul concurenților, respectiv numărul relațiilor pe care și le amintește comisia. Pe fiecare din următoarele M linii se află câte două numere naturale nenule i și j, având semnificația: concurentul cu numărul de concurs i a fost în clasament înaintea concurentului cu numărul de concurs j.
Date de ieșire
Fișierul de ieșire competitie.out va conține pe prima linie clasamentul sub forma unui sir de numere naturale nenule nr1, nr2, …, nrN, separate prin câte un spațiu, reprezentând numerele de concurs ale concurenților, în ordine de la primul clasat la ultimul.
Restricții și precizări
1 ≤ N, M ≤ 1000- Se garantează corectitudinea datelor de intrare și faptul ca există totdeauna o soluție.
Exemplul 1:
competitie.in
3 1 1 2
competitie.out
1 2 3
Exemplul 2:
competitie.in
4 2 2 1 3 4
competitie.out
2 1 3 4
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 Competitie:
#include <bits/stdc++.h>
#define nmax 1001
using namespace std;
int a[nmax], b[nmax]; /// relatiile initiale
int viz[nmax]; /// viz[i] = 1 daca i a fost deja pus in clasament
bitset<nmax> f;
int n, m;
void Citire()
{
int i;
ifstream fin("competitie.in");
fin >> n >> m;
for (i = 1; i <= m; i++)
fin >> a[i] >> b[i];
fin.close();
}
void Clasament()
{
int i, pas, k;
ofstream fout("competitie.out");
for (pas = 1; pas <= n; pas++)
{
/// cauta cel mai mic i care nu apare in b[]
/// adica cel mai mic i cu f[i]=0
f.reset();
for (i = 1; i <= m; i++)
f[b[i]] = 1;
for (i = 1; f[i] == 1 || viz[i] == 1; i++)
;
fout << i << " ";
viz[i] = 1;
/// elimin din a[] relatiile care-l contin pe i
for (k = 1; k <= m; k++)
if (a[k] == i) a[k] = b[k] = 0;
}
fout.close();
}
int main()
{
Citire();
Clasament();
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 
.
Rezolvarea problemei #2309 Competitie
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2309 Competitie 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!