Cod sursa(job #2090128)

Utilizator trifangrobertRobert Trifan trifangrobert Data 17 decembrie 2017 17:00:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <vector>
#include <queue>
#define DIM 50010

using namespace std;

int n, m;
int gradint[DIM];
vector <int> graph[DIM];
vector <int> v;
queue <int> q[2];

void BFS()
{
	int p = 0;
	bool ok = false;
	int x, y;
	while (!ok)
	{
		ok = true;
		while (!q[p].empty())
		{
			x = q[p].front();
			v.push_back(x);
			q[p].pop();
			for (int i = 0;i < (int)graph[x].size();++i)
			{
				y = graph[x][i];
				--gradint[y];
				if (gradint[y] == 0)
				{
					ok = false;
					q[1 - p].push(y);
				}
			}
		}
		p = 1 - p;
	}
}

int main()
{
	ifstream fin("sortaret.in");
	ofstream fout("sortaret.out");
	fin >> n >> m;
	int x, y;
	for (int i = 1;i <= m;++i)
	{
		fin >> x >> y;
		graph[x].push_back(y);
		++gradint[y];
	}
	for (int i = 1;i <= n;++i)
		if (gradint[i] == 0)
			q[0].push(i);
	BFS();
	for (vector <int>::iterator it = v.begin();it != v.end();++it)
		fout << *it << " ";
	fin.close();
	fout.close();
	return 0;
}