Pagini recente » Cod sursa (job #2575179) | Cod sursa (job #2451701) | Cod sursa (job #3200115) | Cod sursa (job #808410) | Cod sursa (job #1420666)
// Sortare Topologica - O(N+M)
#include <fstream>
#include <vector>
#include <bitset>
#define Nmax 50099
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int N,M,Tsort[Nmax],x,y;
vector < int > G[Nmax];
bitset < Nmax > viz;
void DFS(int node) {
viz[node] = 1;
for(vector <int>::iterator it = G[node].begin(); it != G[node].end(); ++it)
if(!viz[*it]) DFS(*it);
// S-au parcurs toti fii lui node, deci il pot adauga la sortare
Tsort[++Tsort[0]]=node;
}
void SorteazaTopologic() {
for(int i =1; i <= N; ++i)
if(!viz[i]) DFS(i);
//Solutia a fost generata invers, deci afisez pe dos
for(int i =N; i >=1 ; --i) g << Tsort[i] << ' ';
g << '\n';
}
int main() {
f >> N >> M;
for(int i = 1; i <= M; ++i)
f >> x >> y , G[x].push_back(y); // ATENTIE CA E ORIENTAT!
SorteazaTopologic();
f.close();g.close();
return 0;
}