Cod sursa(job #3336298)

Utilizator diaconescu14diaconescu diaconescu14 Data 24 ianuarie 2026 15:28:09
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.29 kb
// bfs ul este parcurgerea in latime s icum functioneaza ea
// imi iau o lista
//bfss
// #include <iostream>
// #include <vector>
// #include <queue>
// #include <fstream>
//
//
// using namespace std;
// ifstream in("BFS.in");
// ofstream out("BFS.out");
//  vector <int> vecini[101];
// int viz[101];
// int nivel[101];
// vector <int> ordine;
// queue <int> p;
//
// void bfs(int start) {
//     p.push(start);
//     viz[start] = 1;
//     nivel[start] = 0;
//
//     while(!p.empty()) {
//         int k = p.front();
//         p.pop();
//         ordine.push_back(k);
//
//         for(auto i : vecini[k])
//             if(viz[i] == 0)
//             {
//                 viz[i] = 1;
//                 nivel[i] = nivel[k] + 1;
//                 p.push(i);
//
//             }
//     }
// }
//
// int main()
//         {
//             int n , m , x, i, a,b;
//             in>>n>>m>>x;
//             for(i=0;i<m;i++)
//             {
//                 cin>>a>>b;
//                 vecini[a].push_back(b);
//                 vecini[b].push_back(a);
//
//             }
//             bfs(x);
//     for (i = 0 ; i < ordine.size(); i++)
//         out<<ordine[i]<<" ";
//         }

// //merg in adancime si dupa ma intorc si asa parcurg toate varfurile o sa folosesc in implementare recursivitatea
//
// #include<iostream>
// #include<vector>
// #include<fstream>
//
// using namespace std;
// ifstream in("dfs.in");
// ofstream out("dfs.out");
// vector <int> vecini[101];
// int viz[101];
// vector <int> ordine;
//
// void dfs(int nod) {
//     viz[nod] = 1;
//     ordine.push_back(nod);
//     for (auto v : vecini[nod])
//         if (viz[v] == 0){
//         dfs(v);
//     }
//
//  }
// int main() {
//     int n,m,x, a,b,i;
//     in>>n>>m>>x;
//     for(int i=0;i<m;i++) {
//         in>>a>>b;
//         vecini[a].push_back(b);
//         vecini[b].push_back(a);
//
//
//     }
//
//     dfs(x);
//
//     for (i=0; i<n; i++)
//         out<<ordine[i]<<" ";
// }

// SORTAREA TOPOLOGICA asta inseamna ca eu daca am un o muchie intre nodul i si nodul j i trebuie sa apara inaintea lui j la final
// cum m am gandit sa implementez asta numar imi iau gradele pentru fiecare nod si dupa elimin varf cu varf cand nu mai imi pleaca nimic din el)
// pentru asta o sa imi fac o coada

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

using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
vector <int> vecini[50001];
int f[50001], n,m,x,y;
queue <int> q;
vector <int> rezultat;
void bfs() {
    while (!q.empty()) {
        int k = q.front();
        q.pop();
        for (auto v : vecini[k]) {
            f[v]--;
            if (f[v] == 0) {
                q.push(v);
                rezultat.push_back(v);
            }
        }
    }
    if (rezultat.size() == n) {
        for (int i = 0 ; i < rezultat.size() ; i++) {
            out << rezultat[i] << " ";

        }
    }

}
int main() {
    cin>>n>>m;
    for (int i = 0 ; i<m ; i++) {
        in>>x>>y;
        vecini[x].push_back(y);
        f[y] ++;

    }
    for (int i = 1; i <= n ;i ++)
        if (f[i] == 0) {
            rezultat.push_back(i);
            q.push(i);
        }
    bfs();
}