Pagini recente » Cod sursa (job #2542280) | Cod sursa (job #489854) | Cod sursa (job #2714755) | Cod sursa (job #2105267) | Cod sursa (job #3200080)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
vector<int> graf[50001];
int bf[50001];
/*
A program foprogramaban letrehozza az adott grafot.Ezutan a foprogram meghivja a fugvenyt.
A fugvenyen belul deklaralunk egy SOR adatszerkezetett ami tarolja a csucsokat ugy hogy topologikusan rendezhessuk oket,a
vegleges topologiai sorendet az eredmeny vektorban taroljuk.Ezutan inditunk egy forciklust ami a kezdeti csucsokat a SOR
adatszerkezethez hozzaadjuk.A rakovetkezo while ciklus elvegezei a topologikus rendezest alkalamazva a szelessegi bejaras mo
dszeret(BFS modszer).Ezutan kivezzuk a soron levo csucsot majd atteszuk az eredmeny vektorhoz.A whilelon belul letrehozunk
egy for ciklust ami a kivalasztott csucspontbol vegig jarja a szomszedait , csokentve az elek szamat. Ha nincs tobb szomszed akkor
az adott elt hozarendeljuk a sorhoz.A ket ciklus elvegzese utan akkor egy forciklus segitsegevel kiirjuk a vegleges sorendet.
*/
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
void topologikusrendezes(int N) {
queue<int>sor;
vector<int>eredmeny;
for (int i=1;i<=N;i++) {
if (bf[i]==0) {
sor.push(i);
}
}
while (!sor.empty()) {
int csomopont=sor.front();
sor.pop();
eredmeny.push_back(csomopont);
for (int szomszed:graf[csomopont]) {
bf[szomszed]--;
if (bf[szomszed]==0) {
sor.push(szomszed);
}
}
}
for (int i=0;i<N;i++) {
fout<<eredmeny[i]<<" ";
}
}
int main() {
int N,M;
fin>>N>>M;
for (int i=0;i<M;i++) {
int x,y;
fin>>x>>y;
graf[x].push_back(y);
bf[y]++;
}
topologikusrendezes(N);
return 0;
}