Cod sursa(job #2085386)

Utilizator trifangrobertRobert Trifan trifangrobert Data 10 decembrie 2017 01:21:10
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#include <bitset>
#include <deque>
#define DIM 50010

using namespace std;

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

void BFS()
{
	int x;
	while (!q.empty())
	{
		x = q.front();
		q.pop();
		sol.push_back(x);
		if (!graph[x].empty())
		{
			for (int i = 0;i < graph[x].size();++i)
				--gradint[graph[x][i]];
			if (seen[graph[x].front()] == false)
			{
				q.push(graph[x].front());
				seen[graph[x].front()] = true;
				graph[x].pop_front();
			}
		}
	}
}

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);
	}
	for (int i = 1;i <= n;++i)
	{
		if (!graph[i].empty())
			sort(graph[i].begin(), graph[i].end());
		for (int j = 0;j < (int)graph[i].size();++j)
			++gradint[graph[i][j]];
	}
	bool ok = true;
	while (ok)
	{
		ok = false;
		for (int i = 1;i <= n;++i)
			if (gradint[i] == 0 && !seen[i])
			{
				seen[i] = true;
				q.push(i);
				ok = true;
			}
		if (ok)
			BFS();
	}
	for (auto i : sol)
		fout << i << " ";
	fin.close();
	fout.close();
	return 0;
}