Cod sursa(job #589904)

Utilizator t2010tZaharia Teofil t2010t Data 14 mai 2011 12:19:08
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

struct s_node
{
vector <int> ad;
};

int n,m,list[50001],nlist,nlist2;
s_node node[50001];
bool asc[50001];
queue <int> q;

int main()
{
ifstream in("sortaret.in");
ofstream out("sortaret.out");

int i1,x,y;
vector <int>::iterator it1;

in>>n>>m;
for(i1=0;i1<m;i1++)
	{
	in>>x>>y;
	node[x].ad.push_back(y);
	asc[y] = true;
	}

for(i1=1;i1<n+1;i1++)
	if(!asc[i1])
		{
		list[++nlist] = i1;
		nlist2++;
		}

for(i1=1;i1<nlist2+1;i1++)
	{
	q.push(list[i1]);
	while(!q.empty())
		{
		for(it1 = node[q.front()].ad.begin(); it1 != node[q.front()].ad.end(); it1++)
			{
			q.push(*it1);
			list[++nlist] = *it1;
			}
		q.pop();
		}
	}

for(i1=1;i1<nlist+1;i1++)
	out<<list[i1]<<' ';

in.close();
out.close();
return 0;
}