Cod sursa(job #2963898)

Utilizator brianna_enacheEnache Brianna brianna_enache Data 12 ianuarie 2023 09:45:00
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.44 kb
#include <bits/stdc++.h>
#define nmax 50002
using namespace std;

/**
Sortare topologica

La un concurs de cros au participat n
atleti numerotati de la 1 la n.
Nu se stie clasamentul de la final, in
schimb se cunosc m relatii de forma i j
cu semnificatia i a trecut linia de sosire
inaintea lui j.
Sa se determine un posibil clasament.

Ex:
n = 7, m = 6
3 6
5 6
6 1
2 7
3 7
2 1

clasament posibil: 2 3 5 6 1 7 4
clasament posibil: 4 3 5 2 6 1 7

Rezolvare:
Asociem problemei un graf orientat cu n
varfuri (fiecare atlet este un varf in digraf)
si m arce: exista arcul (i, j) daca
atletul i l-a intrecut pe atletul j.

Graful orientat obtinut este aciclic
(adica nu are circuite)

Intr-un graf orientat exista
- lanturi (succesiuni de noduri cu prop.
           ca orice doua noduri alaturate
           din succesiune sunt adiacente,
           dar nu conteaza orientarea
           arcului)
- drumuri : conteaza orientarea, adica
         daca drumul este format din
         varfurile v[1], v[2], ..., v[p],
         atunci exista arcul (v[1],v[2])
         (v[2],v[3]), ..., (v[p-1],v[p])
- ciclu este un lant inchis
- circuit este drum inchis

Algoritmul:
Fiecare nod are trei stari:
- nevizitat
- vizitat prima oara
- finalizat, in sensul ca s-au incheiat de
  vizitat toti adiacentii sai

Parcurgem nodurile de la 1 la n si cand
gasim un nod nevizitat k, efectuam DFS(k)
in care atunci cand un nod este in starea
"finalizat" se va depune in vectorul s.

In final, dupa ce toate nodurile au fost
vizitate, sortarea topologica se gaseste
in vectorul s, de la de dreapta la stanga.
*/
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector<int> L[nmax];
int n, m, viz[nmax];
int s[nmax], p;

void Citire()
{
    int i, j, k;
    fin >> n >> m;
    for (k = 1; k <= m; k++)
    {
        fin >> i >> j;
        L[i].push_back(j);
    }
}
///O(n + m)
void DFS(int k)
{
    viz[k] = 1;
    for (int i : L[k])
        if (viz[i] == 0) DFS(i);
    /// acum s-a terminat de vizitat nodul k
    /// si toti adicentii sai, deci il pun in s
    s[++p] = k;
}
///O(n + m)
void SortTop()
{
    for (int k = 1; k <= n; k++)
        if (viz[k] == 0)
            DFS(k);
    /// afisam s de la dreapta la stanga
    for (int i = n; i >= 1; i--)
        fout << s[i] << " ";
    fout << "\n";
}

int main()
{
    Citire();
    SortTop();
    fin.close();
    fout.close();
    return 0;
}