Pagini recente » Cod sursa (job #75476) | Cod sursa (job #1495422) | Cod sursa (job #1911255) | Cod sursa (job #1927171) | Cod sursa (job #3271486)
#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 () {
cin >> N >> M;
for (int i = 1; i <= M; i++) {
cin >> 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ă
cout << "Topo" << '\n';
for (int i = 1; i <= N; i++) {
cout << topo[i] << " "; // Afișăm nodurile sortate topologic
}
cout << '\n';
return 0;
}