Pagini recente » Cod sursa (job #2943150) | Cod sursa (job #2422304) | Cod sursa (job #1785689) | Cod sursa (job #2684526) | Cod sursa (job #3336305)
// 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() {
in>>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();
}