Cod sursa(job #1818650)

Utilizator Grama911Grama Andrei Grama911 Data 29 noiembrie 2016 17:50:48
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
using namespace std;

FILE *f = fopen("sortaret.in", "r");
FILE *g = fopen("sortaret.out", "w");

const int NMax = 100005;
int N, M, K, Use[NMax], O[NMax];
vector <int> G[NMax];

void Read()
{
	fscanf(f, "%d%d", &N, &M);
	for (int i = 1; i <= M; ++i)
	{
		int x, y;
		fscanf(f, "%d%d", &x, &y);
		G[x].push_back(y);
	}
}

void DFS(int Nod)
{
	Use[Nod] = 1;
	for (int i = 0; i<(int)G[Nod].size(); ++i)
	{
		int Vecin = G[Nod][i];
		if (!Use[Vecin])
			DFS(Vecin);
	}
	O[++K] = Nod;
}

int main()
{
	Read();
	for (int i = 1; i <= N; ++i)
		if (!Use[i])
			DFS(i);
	for (int i = K; i >= 1; --i)
		fprintf(g, "%d ", O[i]);
	fprintf(g, "\n");
	return 0;
}