Cod sursa(job #1134222)

Utilizator bogdanrusRus Bogdan bogdanrus Data 6 martie 2014 11:11:20
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
// Compilare g++ sursa.cpp -o binar
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

#define NMax 50100

//Complexity = O(N+M)

int M, N, R[NMax], deg[NMax], L[NMax];  vector<int> G[NMax];

void sortare (void) {	
	int i, j, k, sizeL, sizeR;
	sizeL=0;
	sizeR=0;
	
	for (i=1; i<=N; ++i) 
	{
		if (deg[i]==0) {
			sizeL++;
			L[sizeL]=i;
		}
	}
	
	for (i=1; i<=sizeL; ++i) 
	{
		for (j=0; j<G[L[i]].size(); ++j)  
		{
			deg[G[L[i]][j]]--;
			if (deg[G[L[i]][j]]==0) {
				//put node G[L[i]][j] into list L and increment sizeL
				sizeL++;
				L[sizeL] = G[L[i]][j];
			}
		}
		sizeR++;
		R[sizeR]= L[i];
	}
	
	for (i=1; i<=N; ++i) 
	{
		printf("%d ",R[i]);
	}
	
}


int main (void) {
	
	int i,a,b;
		
    freopen("sortaret.in", "rt", stdin);
    freopen("sortaret.out", "wt", stdout);
    
    //N - nr of nodes
    //M - nr of connections (edges)
	
    scanf("%d %d\n", &N, &M);
    for(i = 1; i <= M; i++)
        scanf("%d %d", &a, &b), G[a].push_back(b), deg[b]++;
		
	sortare();

return 0;
}