Cod sursa(job #3271486)

Utilizator AlexandruIoan20Moraru Ioan Alexandru AlexandruIoan20 Data 26 ianuarie 2025 12:53:18
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#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;
}