Pagini recente » Cod sursa (job #1752609) | Cod sursa (job #1748301) | Cod sursa (job #507465) | Cod sursa (job #277800) | Cod sursa (job #2963898)
#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;
}