Cod sursa(job #940579)

Utilizator kassay_akosKassay Akos kassay_akos Data 16 aprilie 2013 17:55:00
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std ;
 
#define MAXNR 50100

vector<int> g[MAXNR];
int viz[MAXNR],gol[MAXNR];
int N,M;
 
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");

void citire(){
    cin >> N >> M ;
	// init 
	for (int i = 1 ; i <= N ; i++){
		gol[i]=0;
		viz[i]=0;
	}
	// citire
	int a,b;
    for (int i = 0 ; i < M ; i++)        {
			cin >> a >> b ;
			g[a].push_back(b);
			gol[b]++;
	}
}

void rezolvare(void){
	int i,j,k,x,y,n = 1;
	int que[MAXNR];

	for(i=1 ; i <= N ; i ++)							//pentru a gasi un punct de start
		if (gol[i]==0) que[1] = i ;

	for(i=1 ; i <= N ; i ++){							//pentru a verifica sa am N noduri afisate
		x = que[i];
		for(j=0;j<g[x].size();j++){						//verific toate nodurile sub el
		  y =  g[x][j] ;
		  gol[y] --;	
		  if (gol[y] == 0) {n++;que[n] = y;}
		}
	}

	for(i=1 ; i <= N ; i ++)	
		cout << que[i] << " ";
}

int main(){
    citire();
	rezolvare();
	cout.flush();
    return 0  ;
}