Cod sursa(job #2720361)

Utilizator zerolightningIon Bobescu zerolightning Data 10 martie 2021 19:19:00
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define IPair pair<int,int>

int N, M;

int main()
{
	ifstream f("sortaret.in");
	ofstream g("sortaret.out");
	// Program
	f >> N >> M;
	vector<vector<int>> links(N+1, vector<int>());
	vector<int> levelOfNode(N + 1, -1);
	vector<vector<int>> levels;
	vector<bool> topLevel(N+1,true);

	for (int i = 0; i < M; i++)
	{
		int x, y;
		f >> x >> y;
		links[x].push_back(y);
		topLevel[y] = false;
	}
	for (int i = 1; i <= N; i++)
	{
		if (topLevel[i])
		{
			links[0].push_back(i);
		}
	}
	//delete &topLevel;
	queue<IPair> q;
	q.push(make_pair(0,0));
	while (!q.empty())
	{
		IPair pr = q.front();
		q.pop();
		int node = pr.first;
		int nodeLevel = pr.second;
		if (levelOfNode[node] < nodeLevel)
		{
			levelOfNode[node] = nodeLevel;
			if (levels.size() <= nodeLevel)
			{
				levels.push_back(vector<int>());
			}
			levels[nodeLevel].push_back(node);
		}

		for (auto it = links[node].begin(); it != links[node].end(); it++)
		{
			q.push(make_pair(*it, nodeLevel + 1));
		}

	}

	for (auto it = levels.begin() + 1; it != levels.end(); it++)
	{
		for (auto jt = (*it).begin(); jt != (*it).end(); jt++)
		{
			g << *jt << " ";
		}
	}

	// Exit
	f.close();
	g.close();
	return 0;
}