Cod sursa(job #2529471)

Utilizator mariaghinescu22Ghinescu Maria mariaghinescu22 Data 23 ianuarie 2020 16:01:06
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>

using namespace std;

const int N = 100001;
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];


//rezolvarea cu bfs
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;
}



//rezolvarea cu dfs

bool viz[N];
int st[N];
int varf;

void dfs(int x) {
	viz[x] = true;
	int y;
	for (int p = lst[x]; p != 0; p = urm[p]) {
		y = vf[p];
		if (!viz[y]) dfs(y);
	}
	st[++varf] = x;
}