Cod sursa(job #2273208)

Utilizator cezar.plescaCezar Plesca cezar.plesca Data 31 octombrie 2018 10:38:25
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include <queue>

using namespace std;

int M,N;

vector<int> L[50000];
int* degree;

FILE* g;

void topologicalsort(){
	int nbVisits=0; 
	queue<int> Q;
	for(int i=0;i<N;i++){
		if(degree[i]==0)
			Q.push(i);
	}

	vector<int>::iterator it; 

	while(!Q.empty()){ 
		int nod=Q.front();
		Q.pop();
		fprintf(g,"%d ",nod+1); 
		nbVisits++;
		
		for (it = L[nod].begin(); it != L[nod].end(); ++it) {
			degree[*it]--;
			if(degree[*it]==0)
				Q.push(*it);
		}
	} 
}

int main(){
	FILE* f= fopen("sortaret.in","rt");
	g= fopen("sortaret.out","wt");
	fscanf(f,"%d %d",&N,&M);

	for(int i=0;i<N;i++){
		L[i].clear();
	}

	int x,y;
	degree=(int*)calloc(N,sizeof(int));

	for(int i=0;i<M;i++){
		fscanf(f,"%d %d",&x,&y);
		L[x-1].push_back(y-1);	
		degree[y-1]++; 
	}

	topologicalsort();

	fclose(g);
	fclose(f);
	return 0;
}