Pagini recente » Cod sursa (job #2312076) | Cod sursa (job #1214434) | Cod sursa (job #3149500) | Cod sursa (job #2271259) | Cod sursa (job #2667455)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
vector <int> m[100001];///Lista de muchii
vector <int> st; ///Vectorul final sortat
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int vizitat[100001],N, M;
void DFS(int x)
{
vizitat[x] = 1; ///vizitam nodul curent
for ( int i = 0; i < m[x].size(); i ++ ) ///parcurgem vectorul de muchii al nodului
if ( m[x][i] == 0 ) ///daca am gasit o muchie care nu a fost vizitata
DFS ( m[x][i] ); ///apelam recursiv
st.push_back(x); ///adaugam nodul in vectorul sortat
}
void read()
{
fin >> N >> M;
for ( int i = 1; i <= M; i++)
{
int x,y;
fin >> x >> y; ///actualizam lista de adiacenta
m[x].push_back(y);
}
for ( int i = 1; i <= N; i++)
if (vizitat[i]==0) ///daca am gasit un nod nevizitat
DFS(i); ///il parcurgem in adancime
for ( int i = st.size()-1; i >= 0; i-- ) ///afisam vectorul in urma sortarii topologice
fout<< st[i] << " ";
}
int main()
{
read();
return 0;
}