Cod sursa(job #1899210)

Utilizator BonCipBonciocat Ciprian Mircea BonCip Data 2 martie 2017 16:32:03
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <stdio.h>

class list {
	int n, *v;
public:
	list() {
		n = 0;
		v = NULL;
	}
	void push(int el) {
		if ((n & (n-1)) == 0) {
			int max = n ? 2*n : 1;
			int *p = new int[max];
			for (int i = 0; i < n; ++i) {
				p[i] = v[i];
			}
			delete v;
			v = p;
		}
		v[n++] = el;
	}
	int operator[] (int u) {
		return v[u];
	}
	int len() {
		return n;
	}
};

list *G;
int *q, l, r;
bool *viz, *tata;

int main()
{
	FILE *fin, *fout;
	fin = fopen("sortaret.in", "r");
	fout = fopen("sortaret.out", "w");
	
	int N, M;
	fscanf(fin, "%d%d", &N, &M);
	
	G = new list[N + 1]();
	tata = new bool[N + 1]();
	for (int i = 1; i <= M; ++i) {
		int x, y;
		fscanf(fin, "%d%d", &x, &y);
		G[x].push(y);
		tata[y] = 1;
	}
	
	q = new int[N + 1];
	viz = new bool[N + 1];
	for (int i = 1; i <= N; ++i) {
		if (!tata[i]) {
			q[r++] = i;
			viz[i] = 1;
		}
	}
	
	while (r != l) {
		int nod = q[l];
		fprintf(fout, "%d ", nod);
		for (int i = 0; i < G[nod].len(); ++i) {
			if (!viz[G[nod][i]]) {
				viz[G[nod][i]] = 1;
				q[r++] = G[nod][i];
			}
		}
		++l;
	}
	
	fclose(fin);
	fclose(fout);
	return 0;
}