Cod sursa(job #2530461)

Utilizator gruhtenZinnenberg Gruhten gruhten Data 24 ianuarie 2020 20:23:50
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

#define Lim 1048576
const int dim=100002;

FILE *f=freopen("sortaret.in","r",stdin);

char buf[Lim];

int pos=0;

int n,m,a,b,i,grad[dim],q[dim],j,k=0;

vector<int> vecin[dim];

inline void cit(int &nr)
{
    nr=0;
    while(buf[pos]<'0' || buf[pos]>'9')
        if(++pos==Lim)
            fread(buf,1,Lim,stdin),pos=0;

    while(buf[pos]>='0'&& buf[pos]<='9')
    {
        nr=(nr<<1)+(nr<<3)+buf[pos]-48;

        if(++pos==Lim)
            fread(buf,1,Lim,stdin),pos=0;

    }

}

int main()
{
    freopen("sortaret.out","w",stdout);

    cit(n);
    cit(m);

  for(i=1;i<=m;i++)
  {
      cit(a);
      cit(b);
      vecin[a].push_back(b);
       grad[b]++;
  }

  for(i=1;i<=n;i++)
    if(grad[i]==0)
        q[++k]=i;

  for(i=1;i<=k;i++)
  {
      m=q[i];

      for(j=0;j<vecin[m].size();j++)
      {
          grad[vecin[m][j]]--;

          if(grad[vecin[m][j]]==0)
             q[++k]=vecin[m][j];

      }
  }

  for(i=1;i<=n;i++)
    printf("%d ",q[i]);

}