Cod sursa(job #2090127)

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

using namespace std;

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

void BFS()
{
	bool gata = false;
	int p = 0;
	while (!gata)
	{
		gata = true;
		while (!q[p].empty())
		{
			int x = q[p].front();
			sol.push_back(x);
			q[p].pop();
			for (int i = 0; i < (int)graph[x].size(); ++i)
			{
				int y = graph[x][i];
				/*graph[x][i] = graph[x].back();
				graph[x].pop_back();*/
				--gradint[y];
				if (gradint[y] == 0)
				{
					gata = 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 (!graph[i].empty())
			sort(graph[i].begin(), graph[i].end());
	}
	for (int i = 1;i <= n;++i)
	{
		if (gradint[i] == 0)
		{
			q[0].push(i);
		}
	}
	BFS();

	for (auto i : sol)
		fout << i << " ";
	fin.close();
	fout.close();
	return 0;
}