Cod sursa(job #1889704)

Utilizator jordan1998Jordan jordan1998 Data 22 februarie 2017 20:49:06
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define buffs 1048576
FILE *f=freopen("sortaret.in","r",stdin);
char buff[buffs];
int pos=0;
int n,m,a,b,i,_g[50002],q[50002],lq=0;
std::vector<int> v[50002];
inline void read(int &nr)
{
    nr=0;
    while(buff[pos]<'0'||buff[pos]>'9') if(++pos==buffs) fread(buff,1,buffs,stdin),pos=0;
    while(buff[pos]>='0'&&buff[pos]<='9')
    {
        nr=(nr<<1)+(nr<<3)+buff[pos]-48;
        if(++pos==buffs) fread(buff,1,buffs,stdin),pos=0;
    }
}
int main()
{ freopen("sortaret.out","w",stdout);
   fread(buff,1,buffs,stdin),pos=0;
   read(n);read(m);
  for(i=1;i<=m;i++)
  {
      read(a);read(b);
      v[a].push_back(b);_g[b]++;
  }
  for(i=1;i<=n;i++)
    if(_g[i]==0) q[++lq]=i;
  for(i=1;i<=lq;i++)
  {   m=q[i];
      a=v[m].size();
      for(b=0;b<a;b++)
      {_g[v[m][b]]--;
       if(_g[v[m][b]]==0) q[++lq]=v[m][b];
      }
  }
  for(i=1;i<=n;i++)
    printf("%d ",q[i]);
}