Cod sursa(job #2529467)

Utilizator mariaghinescu22Ghinescu Maria mariaghinescu22 Data 23 ianuarie 2020 15:55:01
Problema Sortare topologica Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>

using namespace std;

const int N = 50001;
int n, m, nr, q[N], nrp[N];
int vf[2 * N], lst[N], urm[2 * N];

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

void add(int x, int y) {
	vf[++nr] = y;
	urm[nr] = lst[x];
	lst[x] = nr;
	nrp[y]++;
}

struct comp{
	int x, y;
}v[N];

int main() {
	int st = 0, dr = -1;
	in >> n >> m;
	for (int i = 1; i <= m; i++) {
		in >> v[i].x >> v[i].y;
		add(v[i].x, v[i].y);
	}
	for (int i = 1; i <= n; i++)
		if (nrp[i] == 0) q[++dr] = i;
	int x, y;
	while (st <= dr) {
		x = q[st++];
		//prelucram x
		for (int p = lst[x]; p != 0; p = urm[p]) {
			y = vf[p];
			nrp[y]--;
			if (nrp[y] == 0) q[++dr] = y;
		}
	}
	for (int i = 0; i < n; i++) out << q[i] << ' ';
	return 0;
}