Cod sursa(job #940570)

Utilizator kassay_akosKassay Akos kassay_akos Data 16 aprilie 2013 17:29:38
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 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 = 0 ; 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-1].push_back(b-1);
			gol[b-1]++;
	}
}

void rezolvare(void){
	int i,j,k;

	for(i=0 ; i < N ; i ++)							//pentru a verifica sa am N noduri afisate
		for(j=0;j<N;j++)							// pentru a gasit primul nod bun
			if (gol[j]==0 && viz[j]==0){
				viz[j]=1;
				cout << j+1 <<" ";
				for(k=0;k < g[j].size();k++)			//pentru a scadea cele care nu mai au parinte
					gol[ g[i][k] ]--;				
				break;
			}
}

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