Cod sursa(job #1899270)

Utilizator BonCipBonciocat Ciprian Mircea BonCip Data 2 martie 2017 17:04:18
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 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;
bool *viz;
int *L, sp;

void dfs(int u)
{
	if (!viz[u]) {
		viz[u] = 1;
		for (int i = 0; i < G[u].len(); ++i) {
			dfs(G[u][i]);
		}
		L[sp++] = u;
	}
}

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]();
	for (int i = 1; i <= M; ++i) {
		int x, y;
		fscanf(fin, "%d%d", &x, &y);
		G[x].push(y);
	}
	
	viz = new bool[N + 1]();
	L = new int[N]();
	for (int i = 1; i <= N; ++i) {
		dfs(i);
	}
	for (int i = N - 1; i >= 0; --i) {
		fprintf(fout, "%d ", L[i]);
	}
	fprintf(fout, "\n");
	
	fclose(fin);
	fclose(fout);
	return 0;
}