Pagini recente » Cod sursa (job #2827018) | Cod sursa (job #2418430) | Cod sursa (job #2167727) | Cod sursa (job #2975398)
#include <bits/stdc++.h>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
struct degreeVertex{
int inDegree = 0;
int Vertex;
};
bool operator <(const degreeVertex &a, const degreeVertex &b){
return a.inDegree > b.inDegree;
}
const int NMAX = 50001;
vector <int> vecinity[NMAX+3];
priority_queue<degreeVertex> pq;
int degree[NMAX+3];
bool contains(int from, int to){
for(auto crt: vecinity[from]){
if(crt == to){
return true;
}
}
return false;
}
int main()
{
int n, m;
in >> n >> m;
for(int i = 0; i < m; i++){
int from, to;
in >> from >> to;
if(!contains(from, to)){
vecinity[from].push_back(to);
degree[to]++;
}
}
for(int i = 1; i <= n; i++){
degreeVertex temp;
temp.inDegree = degree[i];
temp.Vertex = i;
pq.push(temp);
}
for(int i = 1; i <= n; i++){
degreeVertex temp;
temp.Vertex = pq.top().Vertex;
temp.inDegree = pq.top().inDegree;
pq.pop();
for(auto aux: vecinity[temp.Vertex]){
degree[aux]--;
degreeVertex crt;
crt.inDegree = degree[aux];
crt.Vertex = aux;
pq.push(crt);
}
out << temp.Vertex << " ";
}
return 0;
}