# PBinfo #2309 – Competitie – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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

## Cod sursă C++

```cpp
#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;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2309)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2309/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2309/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)