Cod sursa(job #2841256)

Utilizator Adiiii4231Ravas Adrian Georgel Adiiii4231 Data 29 ianuarie 2022 14:13:55
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fi("sortaret.in");
ofstream fo("sortaret.out");

int n, m;
vector<vector<int>> a;
vector<int> g;

void topsort()
{
	queue<int> q;
	for (int i = 1; i <= n; i++)
	{
		if (g[i] == 0)
		{
			q.push(i);
		}
	}
	while (!q.empty())
	{
		int s = q.front();
		q.pop();
		for (int i = 1; i < a[s].size(); i++)
		{
			g[a[s][i]]--;
			if (g[a[s][i]] == 0)
			{
				q.push(a[s][i]);
			}
		}
		fo << s << " ";
	}
}

int main()
{
	fi >> n >> m;
	for (int i = 0; i <= n; i++)
	{
		g.push_back(0);
		vector<int> x(1, 0);
		a.push_back(x);
	}
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		fi >> x >> y;
		int aux = 1;
		for (int j = 1; j < a[x].size(); j++)
		{
			if (a[x][j] == y)
			{
				aux = 0;
			}
		}
		if (aux == 1)
		{
			a[x].push_back(y);
			g[y]++;
		}
	}
	topsort();
}