Cod sursa(job #964646)

Utilizator RoxanaIstrateIstrate Roxana RoxanaIstrate Data 21 iunie 2013 20:05:53
Problema Sortare topologica Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <queue>
#define max 100000
#define max2 50000
#define max3 100
using namespace std;
struct nodes{
	int neigb[max3];
	int k;
};
int number_of_nodes, number_of_edges;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int inarcs[max2];
nodes node[max];
void sortaret(){
	
	queue<int> myqueue;
	int i;
	for(i = 0; i < number_of_nodes; i++){
		if(inarcs[i] == 0){
			myqueue.push(i);
			//cout<<i<<"\n";
		}
	}
	while(!myqueue.empty()){
		int nod = myqueue.front();
		myqueue.pop();
		fout<<nod+1<<" ";
		for(i = 0; i < node[nod].k; i++){
			inarcs[node[nod].neigb[i]]--;
			if(inarcs[node[nod].neigb[i]] == 0){
				myqueue.push(node[nod].neigb[i]);
			}
		}
		
	}
}
int main(){
	
	int i, x, y;
	fin>>number_of_nodes>>number_of_edges;
	for(i = 0; i < number_of_nodes; i++){
		inarcs[i] = 0;
		node[i].k = 0;
	}
	for(i = 0; i < number_of_edges; i++){
		fin>>x>>y;
		x--;
		y--;
		node[x].neigb[(node[x].k)++] = y;
		inarcs[y]++;
	}
	sortaret();
	return 0;
}