Cod sursa(job #2031148)

Utilizator robuvedVictor Robu robuved Data 2 octombrie 2017 19:35:49
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream in("sortaret.in");
ofstream out("sortaret.out");
class Graph
{
	vector<vector<int>> adj;
	vector<int> in_count;
public:
	Graph(int n) : adj(n, vector<int>()), in_count(n, 0){}
	void AddEdge(int u, int v)
	{
		adj[u].push_back(v);
		in_count[v]++;
	}
	void PrintTopologicalSorting()
	{
		queue<int> q;
		for (int i = 0; i < in_count.size(); i++)
		{
			if (!in_count[i])
			{
				q.push(i);
			}
		}
		while (!q.empty())
		{
			int node = q.front();
			q.pop();
			out << node + 1 << ' ';

			for (int i = 0; i < adj[node].size(); i++)
			{
				int v = adj[node][i];
				in_count[v]--;
				if (!in_count[v])
					q.push(v);
			}
		}
	}
};
int main()
{
	int N, M;
	in >> N >> M;
	Graph g(N);
	for (int i = 0; i < M; i++)
	{
		int u, v;
		in >> u >> v;
		u--; v--;
		g.AddEdge(u, v);
	}
	g.PrintTopologicalSorting();
}