Pagini recente » Cod sursa (job #2731796) | Cod sursa (job #2879117) | Cod sursa (job #2233826) | Cod sursa (job #3210034) | Cod sursa (job #2660615)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int n, m;
vector <int> * lv;
int * in_deg;
bool * removed;
queue <int> q;
vector <int> topological_order;
void topological_sort(){
while(!q.empty()){
int node = q.front();
q.pop();
removed[node] = 1;
topological_order.push_back(node);
for(int i = 0; i < lv[node].size(); i++){
int next_node = lv[node][i];
if(!removed[next_node]){
in_deg[next_node] -= 1;
if(!in_deg[next_node])
q.push(next_node);
}
}
}
}
int main(){
f >> n >> m;
lv = new vector <int>[n + 1];
in_deg = new int[n + 1];
removed = new bool[n + 1];
for(int i = 0; i <= n; i++){
removed[i] = 0;
in_deg[i] = 0;
}
int x, y;
for(int i = 0; i < m; i++){
f >> x >> y;
lv[x].push_back(y);
in_deg[y] += 1;
}
for(int i = 1; i <= n; i++)
if(!in_deg[i])
q.push(i);
topological_sort();
for(int i = 0; i < topological_order.size(); i++)
g << topological_order[i] << " ";
return 0;
}