Pagini recente » Istoria paginii runda/polama | Cod sursa (job #2575294) | Profil aIexpetrescu | Cod sursa (job #3135892) | Cod sursa (job #2299343)
#include <cstdio>
#include <vector>
#define NMAX 50005
using namespace std;
const char inname[] = "sortaret.in";
const char outname[] = "sortaret.out";
FILE *fin = fopen(inname, "r");
FILE *fout = fopen(outname, "w");
int n, m, vizitat[NMAX];
struct Lista{
vector<int> vecini;
};
Lista L[NMAX];
vector<int> sortareFinala;
void citire();
void sortareTopologica();
void DFS(int);
void afisare();
int main(){
citire();
sortareTopologica();
afisare();
fclose(fin);
fclose(fout);
return 0;
}
void citire(){
int i, x, y;
fscanf(fin, "%d", &n);
fscanf(fin, "%d", &m);
for(i=1; i<=m; i++){
fscanf(fin, "%d", &x);
fscanf(fin, "%d", &y);
L[x].vecini.push_back(y);
}
}
void sortareTopologica(){
int i;
for(i=1; i<=n; i++)
if(vizitat[i] == 0)
DFS(i);
}
void DFS(int k){
int i;
vizitat[k] = 1;
for(i=0; i<L[k].vecini.size(); i++)
if(vizitat[L[k].vecini[i]] == 0)
DFS(L[k].vecini[i]);
sortareFinala.push_back(k);
}
void afisare(){
int i;
for(i=sortareFinala.size()-1; i>=0; i--)
fprintf(fout, "%d ", sortareFinala[i]);
fprintf(fout, "\n");
}