Cod sursa(job #3187542)

Utilizator AlessiaFrunzaAlessia Frunza AlessiaFrunza Data 29 decembrie 2023 13:53:55
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.68 kb
// #include <iostream>
// #include <queue>
// #include <fstream>

// using namespace std;
// ifstream fin("sortaret.in");
// ofstream fout("sortaret.out");

// int main() { 

//     int numar_noduri;
//     int numar_arce;
//     cin >> numar_noduri >> numar_arce;

//     int noduri_grad_interne[numar_arce];
//     int noduri_grad_externe[numar_arce];
//     int grad_intern[numar_noduri];
//     queue<int> coada_grad_zero;

//     for (int i = 1; i <= numar_noduri; i++) {
//         grad_intern[i] = 0;
//     }

//     for (int i = 0; i < numar_arce; i++) {
//         cin >> noduri_grad_externe[i] >> noduri_grad_interne[i];
//         grad_intern[noduri_grad_interne[i]]++;
//     }

//     // fin.close();
//     int count = 0;
//     for (int i = 1; i <= numar_noduri; i++) {
//         if (grad_intern[i] == 0 ) 
//             coada_grad_zero.push(i);         
//     }

//     while(!coada_grad_zero.empty()) {

//         int nod_curent = coada_grad_zero.front();
//         cout << nod_curent << " ";
//         count++;
//         coada_grad_zero.pop();

//         grad_intern[nod_curent] = 0;

//         for (int i = 0; i < numar_arce; i++) {
//             if (noduri_grad_externe[i] == nod_curent) {
//                 grad_intern[noduri_grad_interne[i]]--;
            
//                 if (grad_intern[noduri_grad_interne[i]] == 0) {
//                     coada_grad_zero.push(noduri_grad_interne[i]);
//                 }
//             }
//         }        
//     }

    // if (count == numar_noduri) {
    //     cout << "TRUE" << " ";
    // } else if (count < numar_noduri){
    //     cout << "MAI PUTINE" << " ";
    // } else if (count > numar_noduri) {
    //     cout << "MAI MULTE" << " ";
    // }

//     // fout.close();
//     return 0;
// }


#include <iostream>
#include <fstream>
#include <queue>

using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int main() { 
    int numar_noduri, numar_arce;
    fin >> numar_noduri >> numar_arce;

    vector<int> grad_intern(numar_noduri, 0);
    vector<vector<int>> adiacenta(numar_noduri);

    for (int i = 0; i < numar_arce; i++) {
        int x, y;
        fin >> x >> y;
        x--; y--; 
        adiacenta[x].push_back(y);
        grad_intern[y]++;
    }

    queue<int> coada;

    for (int i = 0; i < numar_noduri; i++) {
        if (grad_intern[i] == 0) {
            coada.push(i);
        }
    }

    while (!coada.empty()) {
        int nod = coada.front();
        coada.pop();
        fout << (nod + 1) << " ";
        for (int vecin : adiacenta[nod]) {
            grad_intern[vecin]--;
            if (grad_intern[vecin] == 0) {
                coada.push(vecin);
            }
        }
    }

    return 0;
}