Pagini recente » Cod sursa (job #2935340) | Cod sursa (job #2390051) | Cod sursa (job #2136205) | Cod sursa (job #2600237) | Cod sursa (job #3271487)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int N, M, x, y, a[1001][1001];
int timp[1001], viz[1001], t, topo[1001];
void citire () {
fin >> N >> M;
for (int i = 1; i <= M; i++) {
fin >> x >> y;
a[x][y] = 1; // Folosim matricea de adiacență
}
for (int i = 1; i <= N; i++) {
topo[i] = i; // Inițializăm ordinea inițială a nodurilor
}
}
void dfs(int x) {
viz[x] = 1;
// Explorăm vecinii lui x
for (int i = 1; i <= N; i++) {
if (a[x][i] == 1 && !viz[i])
dfs(i);
}
t++; // Incrementăm timpul la finalizarea nodului
timp[x] = t; // Stocăm timpul de finalizare pentru nodul x
}
void sortaret() {
// Sortăm nodurile în funcție de timpul de finalizare în ordinea descrescătoare
for (int i = 1; i < N; i++) {
for (int j = i + 1; j <= N; j++) {
if (timp[topo[i]] < timp[topo[j]]) {
swap(topo[i], topo[j]); // Sortăm și topo[i] pentru a menține ordinea
}
}
}
}
int main () {
citire();
// Apelăm DFS pentru toate nodurile
for (int i = 1; i <= N; i++) {
if (!viz[i])
dfs(i);
}
// Sortăm în funcție de timpul de finalizare
sortaret();
// Afișăm nodurile în ordinea topologică
for (int i = 1; i <= N; i++) {
fout << topo[i] << " "; // Afișăm nodurile sortate topologic
}
return 0;
}