Cod sursa(job #1750569)

Utilizator bogdanluncasubogdan bogdanluncasu Data 30 august 2016 15:05:04
Problema Sortare topologica Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
using namespace std;
#define SIZE 10000
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;
	cin>>n>>m;
	for(i=1;i<=m;i++)
		cin>>x,cin>>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++){
		cout<<l[i]<<" ";
	}
	
}