Cod sursa(job #2720368)

Utilizator zerolightningIon Bobescu zerolightning Data 10 martie 2021 19:24:06
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 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<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));
	int maxNode = 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;
			maxNode = max(maxNode, nodeLevel);
		}

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

	}
	vector<vector<int>> levels(maxNode+1,vector<int>());
	for (int i = 1; i <= N; i++)
	{
		levels[levelOfNode[i]].push_back(i);
	}
	
	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;
}