Cod sursa(job #964631)

Utilizator RoxanaIstrateIstrate Roxana RoxanaIstrate Data 21 iunie 2013 19:44:00
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <queue>
#define max 100000
#define max2 50000
using namespace std;
struct pairs{
	int x, y;
	void to_string(){
		cout<<x<<" "<<y<<"\n";
	}
};
int number_of_nodes, number_of_edges;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int inarcs[max2];
pairs arcs[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 node = myqueue.front();
		myqueue.pop();
		fout<<node+1<<" ";
		for(i = 0; i < number_of_edges; i++){
			//cout<<arcs[i].x<<" ";
			if (arcs[i].x == node){
				//cout<<"da\n";
				inarcs[arcs[i].y]--;
				if(inarcs[arcs[i].y] == 0){
					myqueue.push(arcs[i].y);
					//cout<<node<<" "<<arcs[i].y<<" \n";
				}
			}
		}
		
	}
}
int main(){
	
	int i;
	fin>>number_of_nodes>>number_of_edges;
	for(i = 0; i < number_of_nodes; i++){
		inarcs[i] = 0;
	}
	for(i = 0; i < number_of_edges; i++){
		fin>>arcs[i].x>>arcs[i].y;
		arcs[i].x--;
		arcs[i].y--;
		inarcs[arcs[i].y]++;
	}
	sortaret();
	return 0;
}