Cod sursa(job #584743)

Utilizator t2011tVasilescu Popescu t2011t Data 26 aprilie 2011 16:24:56
Problema Sortare topologica Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#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);
}