Cod sursa(job #3033315)

Utilizator 222cezarCezar Stilpeanu 222cezar Data 23 martie 2023 18:46:15
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

#define FILE "sortaret"

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

#define N 50050
#define M 100100

struct el {
	int vf, urm;
};

el g[2 * M];
int lst[N], nrp[N];
int nr;

void adauga(int u, int v) {
	g[++nr].vf = v;
	g[nr].urm = lst[u];
	lst[u] = nr;
	nrp[v]++;
}

//parcurgere for(int p = lst[u]; p != 0; p = g[p].urm) { int v = v[p].vf; }

queue<int> q;
vector<int> topo;

void bfs() {
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int p = lst[u]; p != 0; p = g[p].urm) {
			int v = g[p].vf;
			if(--nrp[v] == 0) {
				topo.push_back(v);
				q.push(v);
			}
		}
	}
}

int main() {
	int n, m;
	in >> n >> m;

	for(int i = 1; i <= m; i++) {
		int u, v;
		in >> u >> v;
		adauga(u, v);
	}

	for(int i = 1; i <= n; i++) {
		if(nrp[i] == 0) {
			q.push(i);
			topo.push_back(i);
		}
	}

	bfs();
	
	for(auto nod : topo)
		out << nod << ' ';
}