Cod sursa(job #1750571)

Utilizator bogdanluncasubogdan bogdanluncasu Data 30 august 2016 15:07:31
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#define SIZE 20000
int a[SIZE][SIZE];
int l[SIZE],s[SIZE];
bool inmuchii(int node,int n){
	for(int j=1;j<=n;j++)
		if(a[j][node]==1){
			return false;
		}
	return true;
	
}
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][y]=1;
			
	
	int in,sindex=0,lindex=0;
	
	for(i=1;i<=n;i++){
		in=0;
		for(j=1;j<=n;j++)
			if(a[j][i]==1){
				in=1;
			}
		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(a[node][j]==1){
					a[node][j]=0;
					if(inmuchii(j,n)){
						s[sindex++]=j;
					}
				}
			}
		
	}
	
	for(i=0;i<lindex;i++){
		printf("%d ",l[i]);
	}
	
}