Cod sursa(job #182791)

Utilizator znakeuJurba Andrei znakeu Data 21 aprilie 2008 12:45:32
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <stdio.h>
#include <string.h>
#define MAXM 100050
#define MAXN 50050

struct muchie
{
	int x,y;	
};

muchie a[MAXM];
int vizitat[MAXN];
int count[MAXN];
int * v[MAXN];
int n,m;
int r[MAXN],k;

inline void parsarelinie(int *a, int *b)  
{  
    char s[32]; int j=0,x=0,y=0;  
    fgets(s,32,stdin);  
      
    while (s[j]>='0' && s[j]<='9')  
        x=x*10+s[j++]-'0';  
      
    j++;  
      
    while (s[j]>='0' && s[j]<='9')  
        y=y*10+s[j++]-'0';  
    *a=x; *b=y;  
}  

void citire()
{
	int i;
	
	parsarelinie(&n,&m);
	
	for (i=0; i<m; ++i)
	{
		parsarelinie(&a[i].y,&a[i].x);
		++count[a[i].x];
	}
	
	for (i=1; i<=n; ++i)
	{
		v[i] = new int[count[i]+2];
		v[i][0] = 0;
	}
	
	for (i=0; i<m; ++i)
		v[ a[i].x ] [ ++v[ a[i].x ] [0] ] = a[i].y;
}

void wtf(int p)
{
	int i;
	
	vizitat[ p ] = 1;
	
	for (i=1; i <= v[p][0]; ++i)
		if ( ! vizitat [ v[p][i] ] )
			wtf( v[p][i] );
	
	r[k++]=p;	
}

void rezolvare()
{
	int i;
	
	for (i=1; i <= n; ++i)
		if ( !vizitat[ i ] )
			wtf( i );
}

void afisare()
{
	int i;
	
	printf("%d",r[0]);
	
	for (i=1; i<k; ++i)
		printf(" %d",r[i]);
	
	printf("\n");	
}

int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	
	citire();
	rezolvare();
	afisare();
	fclose(stdin);
	fclose(stdout);
	return 0;
}