Cod sursa(job #1750612)

Utilizator bogdanluncasubogdan bogdanluncasu Data 30 august 2016 16:26:52
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <vector>
#include <algorithm>
#define SIZE 50001
using namespace std;
 
vector<int> a[SIZE];
int l[SIZE],s[SIZE],deg[SIZE],n;
bool inmuchii(int node){
		if(deg[node]!=0){
			return false;
		}
		return true;	
}
void afiseaza(vector<int> v){
	for(vector<int>::iterator it = v.begin(); it != v.end(); ++it){
		cout<<*it<<" ";
	}
	cout<<endl;
	
}
int main() {
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	int i,j,c,n,x,y,m;
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++)
		scanf("%d %d",&x,&y),deg[y]++,a[x].push_back(y);	
	int sindex=0,lindex=0;
	for(i=1;i<=n;i++){ 
		if(deg[i]==0)s[sindex++]=i;
	}
	while(s[0]!=0){
		int node=s[--sindex];
		s[sindex]=0;
		l[lindex++]=node;
			for(vector<int>::iterator it=a[node].begin();it<a[node].end();it++){
					int val=*it;
					int numberof=count(a[node].begin(),a[node].end(),val);
					a[node].erase(remove(a[node].begin(), a[node].end(), val), a[node].end());
					it--;
					deg[val]-=numberof;
					if(inmuchii(val)){
						s[sindex++]=val;
					}
			}
		
	}
	
	for(i=0;i<lindex;i++){
		printf("%d ",l[i]);
	}
	
}