Cod sursa(job #1438663)

Utilizator RanKBrinduse Alexandru RanK Data 20 mai 2015 15:55:25
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 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"

vector<vector<int>> adjMat2 = vector<vector<int>>();
int grades[50000];

void DFS(int start, list<int> *q)
{
	for(int i=0; i<adjMat2[start].size(); i++)
	{
		DFS(adjMat2[start][i], q);		
	}
	if(grades[start] <= 1)
		q->push_front(start);
	else
		grades[start] --;
}
 
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);
	
	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);
	}

	for(int i=0; i<n; i++)
	{
		if(grades[i])
			continue;
		list<int> q = list<int>();
		DFS(i, &q);
		for (std::list<int>::const_iterator it = q.begin(), end = q.end(); it != end; ++it) {
			int nr = *it;
			if(grades[nr] <= 1)
				fprintf(pFout, "%d ", nr+1);
			else
				grades[nr] --;
		}
		q.clear();
	}
	fprintf(pFout, "\n");

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