Pagini recente » Cod sursa (job #1322887) | Cod sursa (job #2318657) | Cod sursa (job #674146) | Cod sursa (job #401855) | Cod sursa (job #2666800)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
vector <int> M[100001];///Lista de muchii
vector <int> Sortare; ///Vectorul final sortat
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int Viz[100001], X1, X2;
int NrComponenteConexe, Dimensiune, N1, N2;
void Dfs(int x)
{
Viz[x] = 1; ///vizitam nodul curent
for ( int i = 0; i < M[x].size(); i ++ ) ///parcurgem vectorul de muchii al nodului
if ( Viz[ M[x][i] ] == 0 ) ///daca am gasit o muchie care nu a fost vizitata
Dfs ( M[x][i] ); ///apelam recursiv
Sortare.push_back(x); ///adaugam nodul in vectorul sortat
}
int main()
{
f >> N1 >> N2;
for ( int i = 1; i <= N2; i++)
{
f >> X1 >> X2; ///actualizam lista de adiacenta
M[X1].push_back(X2);
}
for ( int i = 1; i <= N1; i++)
if (Viz[i]==0) ///daca am gasit un nod nevizitat
Dfs(i); ///il parcurgem in adancime
Dimensiune = Sortare.size() - 1; ///aflam dimensiunea vectorului sortat
for ( int i = Dimensiune; i >= 0; i-- ) ///afisam vectorul in urma sortarii topologice
g << Sortare[i] << " ";
return 0;
}