Cod sursa(job #1554093)

Utilizator cosminionutCosmin Ionut cosminionut Data 20 decembrie 2015 21:35:37
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;



/*void citire()
{
	
}
void afisare()
{
	for (vector<int>::iterator i = L.begin();i != L.end();i++)
		g << *i << " ";
}*/
int main()
{
	//ios::sync_with_stdio(false);
	//ifstream f("sortaret.in");
	//ofstream g("sortaret.out");
	FILE *f;f = fopen("sortaret.in", "r");
	FILE *g;g = fopen("sortaret.out", "w");
	
	vector<int> Graf[50001], L, S;
	int incomingNodes[50001];
	memset(incomingNodes, 0, sizeof(incomingNodes));
	int N, M;

	//citire();
	int i, x, y;
	fscanf(f, "%d%d", &N, &M);
	//f >> N >> M;
	for (i = 0;i < M;i++)
	{
		//f >> x >> y;
		fscanf(f, "%d%d", &x, &y);
		incomingNodes[y] += 1;
		Graf[x].push_back(y);
	}
	for (i = 1;i <= N;i++)
		if (incomingNodes[i] == 0)
			S.push_back(i);


	int n, m;
	while (!S.empty())
	{
		n = S.back();
		S.pop_back();
		L.push_back(n);
		while (!Graf[n].empty())
		{
			m = Graf[n].back();
			incomingNodes[m]--;
			if(incomingNodes[m]==0)	S.push_back(m);
			Graf[n].pop_back();
		}
	}

	for (vector<int>::iterator i = L.begin();i != L.end();i++)
		fprintf(g, "%d ", *i);
		//g << *i << " ";
	return 0;
}