Pagini recente » Cod sursa (job #1625411) | Cod sursa (job #2698312) | Cod sursa (job #2961455) | Cod sursa (job #2542312)
#include<fstream>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define NMAX 50001
//in-out
std::ifstream f("sortaret.in");
std::ofstream g("sortaret.out");
//data
std::queue<int> q;
std::vector<int>G[NMAX]; //graph
std::vector<int>in(NMAX);
std::vector<int>sol;
int n, m;
//read data
void readData(){
f >> n >> m;
int x, y;
for(int i = 1; i<=m; i++){
f >> x >> y;
G[x].push_back(y);
in[y] ++;
}
}
//solve problem
void solve(){
for(int i = 1; i<=n; i++){
if(in[i] == 0){
q.push(i);
}
}
while(!q.empty()){
int node = q.front();
q.pop();
sol.push_back(node);
for(const auto& adj : G[node]){
in[adj] --;
if(in[adj] == 0){
q.push(adj);
}
}
}
}
void printSolution(){
for(int i = 0; i<n; i++){
g << sol[i] << ' ';
}
}
int main(){
readData();
solve();
printSolution();
return 0;
}