Mai intai trebuie sa te autentifici.
Cod sursa(job #2436474)
Utilizator | Data | 5 iulie 2019 22:03:15 | |
---|---|---|---|
Problema | Sortare topologica | Scor | 60 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.78 kb |
#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, grad_in[MAX];
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;
grad_in[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 << "Gradul interior al nodurile este: \n";
for(int i = 1; i <= nrNod; i++)
fout << grad_in[i] << " ";
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] && grad_in[i] == 0) //daca nu e vizitat
dfs(i);
afisare_topsort();
}
int main()
{
citire();
// afisare_lista();
TopSort();
return 0;
}