# PBinfo #2123 – Relatii – Rezolvare C++

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

## Enunț

Să considerăm N variabile, denumite cu litere mici ale alfabetului englez, începând cu litera a. Să considerăm de asemenea M relaţii de ordine între aceste N variabile, sub forma:
var1>var2
sau
var1<var2
unde var1 şi var2 sunt două nume de variabile (deci litere mici distincte dintre primele N litere ale alfabetului englez).

Cerința
Scrieţi un program care să ordoneze crescător cele N variabile pe baza celor M relaţii cunoscute.

Date de intrare
Fişierul de intrare relatii.in conţine pe prima linie numerele naturale N, M, separate prin spaţiu. Pe fiecare dintre următoarele M linii este scrisă o relaţie sub forma din enunţ.

Date de ieșire
Fişierul de ieşire relatii.out va conţine o singură linie pe care vor fi scrise N litere mici, neseparate prin spaţii, reprezentând variabilele ordonate crescător. Dacă există mai multe soluţii posibile, se va afişa cea mai mică din punct de vedere lexicografic (prima în dicţionar).

Restricții și precizări
• 2 ≤ N ≤ 10
• 1 ≤ M ≤ 200
• Relaţiile specificate în fişierul de intrare nu conţin spaţii.
• Pentru datele de test există întotdeauna soluţie, nu neapărat unică. 
• Spunem că sirul x1 x2 … xN este mai mic din punct de vedere lexicografic decât şirul y1 y2 … yN dacă există un indice k (1 ≤ k ≤ N) astfel încât xi = yi, pentru orice 1 ≤ i < k şi xk < yk.

Exemplu:
relatii.in

4 5
a<d
a<c
c>d
b>c
b>a
relatii.out

adcb
Explicație

## Cod sursă C++

```cpp
//em. cerchez 100 puncte
#include <bits/stdc++.h>
#define NMax 20
using namespace std;
ofstream fout("relatii.out");
ifstream fin("relatii.in");
int N, M;
int R[NMax][NMax];
int p[NMax];
void citire();
void afisare();
int verif();
int main()
{
int i, j, st, dr, aux;
citire();
for (i=1; i<=N; i++) p[i]=i;
while (1)
      {
      if (verif()) break;
      //generez permutarea urmatoare
      for (j=N-1; p[j]>p[j+1]; j--);
      //maresc p[j]
      for (i=N; p[i]<p[j]; i--);
      //interschimb p[i] cu p[j]
      aux=p[i]; p[i]=p[j]; p[j]=aux;
      //inversez sufixul j+1..N
      for (st=j+1, dr=N; st<dr; st++, dr--)
          {aux=p[st];p[st]=p[dr]; p[dr]=aux;}
      }
afisare();
return 0;
}
void citire()
{
char c1, c2, c3;
int i;
fin>>N>>M;
for (i=0; i<M; i++)
    {
    fin>>c1>>c2>>c3;
    if (c2=='>')
       {R[c1-'a'+1][c3-'a'+1]=1;
        R[c3-'a'+1][c1-'a'+1]=-1;}
        else
        {
        R[c1-'a'+1][c3-'a'+1]=-1;
        R[c3-'a'+1][c1-'a'+1]=1;
        }
    }
}
void afisare()
{
int i;
for (i=1; i<=N; i++)
    fout<<(char)(p[i]-1+'a');
fout<<'\n';
fout.close();
}
int verif()
{
int i, j;
for (i=1; i<N; i++)
    for (j=i+1; j<=N; j++)
        if (R[p[i]][p[j]]==1) return 0;
return 1;
}
```

## Resurse

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