Cod sursa(job #1750585)

Utilizator bogdanluncasubogdan bogdanluncasu Data 30 august 2016 15:42:45
Problema Sortare topologica Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <vector>
#include <algorithm>
#define SIZE 50000
using namespace std;
 
vector<int> a[SIZE];
int l[SIZE],s[SIZE];
bool inmuchii(int node,int n){
	for(int j=1;j<=n;j++)
		if(find(a[j].begin(), a[j].end(),node )!=a[j].end()){
			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),a[x].push_back(y);
			
	
	int in,sindex=0,lindex=0;
	
	for(i=1;i<=n;i++){
		in=0;
		for(j=1;j<=n;j++)
			if(find(a[j].begin(), a[j].end(), i)!=a[j].end()){
				in=1;
				j=n;
			}
		if(in==0){
			s[sindex++]=i;
		}
	
	}
	while(s[0]!=0){
		int node=s[--sindex];
		s[sindex]=0;
		l[lindex++]=node;
			for(j=1;j<=n;j++){
				if(find(a[node].begin(), a[node].end(),j )!=a[node].end()){
					a[node].erase(remove(a[node].begin(), a[node].end(), j), a[node].end());
					if(inmuchii(j,n)){
						s[sindex++]=j;
					}
				}
			}
		
	}
	
	for(i=0;i<lindex;i++){
		printf("%d ",l[i]);
	}
	
}