Pagini recente » Cod sursa (job #1531925) | Monitorul de evaluare | Rating Marinescu Vlad Stefan (Gollm29) | Profil AlinCosmin | Cod sursa (job #584743)
Cod sursa(job #584743)
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct s_node
{
vector <int> asc;
vector <int> dsc;
int val;
int id;
};
int n,m;
int n0,node0[50000];
s_node node[50000];
queue <int> q;
bool comp(s_node a, s_node b);
int main()
{
ifstream in("sortaret.in");
ofstream out("sortaret.out");
int i1;
vector <int>::iterator it1;
int x,y;
in>>n>>m;
for(i1=0;i1<m;i1++)
{
in>>x>>y;
x--; y--;
node[x].dsc.push_back(y);
node[y].asc.push_back(x);
}
for(i1=0;i1<n;i1++)
if(node[i1].asc.empty())
{
node0[n0] = i1;
n0++;
}
for(i1=0;i1<n0;i1++)
{
q.push(node0[i1]);
while(!q.empty())
{
if(!node[q.front()].dsc.empty())
for(it1 = node[q.front()].dsc.begin(); it1 != node[q.front()].dsc.end(); it1++)
{
if(node[*it1].val < node[q.front()].val + 1)
node[*it1].val = node[q.front()].val + 1;
q.push(*it1);
}
q.pop();
}
}
for(i1=0;i1<n;i1++)
node[i1].id = i1;
sort(node, node+n, comp);
for(i1=0;i1<n;i1++)
out<<node[i1].id + 1<<' ';
in.close();
out.close();
return 0;
}
bool comp(s_node a, s_node b)
{
return (a.val < b.val);
}