Cod sursa(job #1438703)

Utilizator RanKBrinduse Alexandru RanK Data 20 mai 2015 17:00:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
  
#include <stdlib.h>
#include <queue>
#include <list>
  
typedef unsigned long long int int64;

using namespace std;

#define IN_FILE_NAME "sortaret.in"
#define OUT_FILE_NAME "sortaret.out"
 
int main()
{   
   FILE *pFin, *pFout;

	pFin = fopen(IN_FILE_NAME, "r");
	pFout = fopen(OUT_FILE_NAME, "w");

	int n,m;

	fscanf(pFin, "%d %d", &n, &m);
	
	vector<vector<int>> adjMat2 = vector<vector<int>>();
	int grades[50000];
	memset(grades, 0, sizeof(grades));
		
	for(int i=0; i<n; i++)
		adjMat2.push_back(vector<int>());

	for(int i=0; i<m; i++)
	{
		int a,b;

		fscanf(pFin, "%d %d", &a, &b);

		a--;b--;
		grades[b]++;
		adjMat2[a].push_back(b);
	}

	list<int> S = list<int>();
	list<int> L = list<int>();

	for(int i=0; i<n; i++)
	{
		if(grades[i])
			continue;
		S.push_back(i);
	}

	while(!S.empty())
	{
		int currNode = S.front();
		S.pop_front();
		L.push_back(currNode);

		while(adjMat2[currNode].size() > 0)
		{
			int nextNode = adjMat2[currNode].back();
			adjMat2[currNode].pop_back();

			grades[nextNode] --;
			if(grades[nextNode] == 0)
				S.push_back(nextNode);
		}
	}

	while(!L.empty())
	{
		int node = L.front();
		L.pop_front();
		fprintf(pFout, "%d ", node+1);
	}
	fprintf(pFout, "\n");	

	fclose(pFin);
	fclose(pFout);
 
    return 0;
}