Pagini recente » Cod sursa (job #3281224) | Cod sursa (job #1179204) | Cod sursa (job #1511108) | Cod sursa (job #1705925) | Cod sursa (job #2436470)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("sortaret.in");
ofstream fout("sortaret.out");
#define MAX 20000
int a[MAX][MAX], nrNod, nrMuchii;
int ordine[MAX], index_ordine;
bool viz[MAX];
void citire(){
//Memoram graful orientat intr-o matrice de adiacenta;
//Coloana 0 va pastra gradul interior al nodului i;
fin >> nrNod >> nrMuchii;
for(int i = 1; i <= nrMuchii; i++){
int x, y;
fin >> x >> y;
a[x][0]++;
a[x][a[x][0]] = y;
}
}
void afisare_lista(){
fout << "Lista de adiacenta este: \n";
for(int i = 1; i <= nrNod; i++){
int grad = a[i][0];
fout << i << ": ";
for(int j = 1; j <= grad; j++)
fout << a[i][j] << " ";
fout << "\n";
}
fout << "\n";
}
void makeset(){
for(int i = 1; i <= nrNod; i++)
viz[i] = 0;
}
void dfs(int nod){
viz[nod] = 1;
int grad = a[nod][0];
for(int j = 1; j <= grad; j++)
if(!viz[a[nod][j]])
dfs(a[nod][j]);
ordine[index_ordine--] = nod;
}
void afisare_topsort(){
// fout << "Ordinea topologica gasita este: ";
for(int i = 1; i <= nrNod; i++)
fout << ordine[i] << " ";
// fout << "\n";
}
void TopSort(){
makeset(); //initializam vec. viz[]
index_ordine = nrNod; //pozitia unde trebuie introdus nodul
for(int i = 1; i <= nrNod; i++)
if(!viz[i]) //daca nu e vizitat
dfs(i);
afisare_topsort();
}
int main()
{
citire();
// afisare_lista();
TopSort();
return 0;
}