Cod sursa(job #1971678)

Utilizator Robert29FMI Tilica Robert Robert29 Data 20 aprilie 2017 20:17:12
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<stdio.h>
#include<vector>
#define N 50001
using namespace std;
FILE*f = fopen("sortaret.in", "r");
FILE*g = fopen("sortaret.out", "w");

vector<int> v[N];
int gr[N], q[N];
int main(){
	int n, m;
    fscanf(f, "%d%d", &n, &m);
	for(int i = 1; i <= m; ++i)
	{
		int x, y;
		fscanf(f, "%d%d", &x, &y);
		v[x].push_back(y);
		++gr[y];
	}

	for(int i = 1; i <= n; ++i)
	{
		if(!gr[i])
		{
			q[++q[0]] = i;
		}
	}

	for(int i = 1; i <= n; ++i)
	{
		int vertice = q[i];
		for(int j = 0; j < v[vertice].size(); ++j)
		{
			if(--gr[v[vertice][j]] == 0)
			{
				q[++q[0]] = v[vertice][j];
			}
		}
	}

	for(int i = 1; i <= n; ++i)
	{
		fprintf(g, "%d ", q[i]);
	}

	fclose(f);
	fclose(g);
	return 0;
}