Cod sursa(job #2781072)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 8 octombrie 2021 13:43:16
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include<cstdio>
const int N=50001,M=100000,L=2000000;
int m,i,a[M],b[M],*g[N],w[N],k,n,t,l;
bool v[N];
char p[L];
inline int A()
{
  	int s=0;
  	for(;p[t]<48;++t);
  	for(;p[t]>47;++t)
  		s=s*10+p[t]-48;
  	return s;
}
inline void S(int x)
{
    int i,d=x>9999?5:x>999?4:x>99?3:x>9?2:1;
    for(i=d-1;i>=0;x/=10,--i)
        p[l+i]=x%10+48;
    p[l+d]=32,l+=d+1;
}
inline void D(int i)
{
    int j;
    for(v[i]=1,j=0;j<w[i];++j)
        if(!v[g[i][j]])
            D(g[i][j]);
    S(i);
}
int main()
{
	freopen("sortaret.in","r",stdin),freopen("sortaret.out","w",stdout),fread(p,1,L,stdin),n=A(),m=A();
    for(i=0;i<m;++i)
        a[i]=A(),b[i]=A(),w[a[i]]++;
    for(i=1;i<=n;w[i++]=0)
    	g[i]=new int[w[i]];
    for(i=0;i<m;++i)
    	g[a[i]][w[a[i]]++]=b[i];
    for(i=1;i<=n;++i)
        if(!v[i])
        	D(i);
    fwrite(p,1,l,stdout);
    return 0;
}