Cod sursa(job #3255872)

Utilizator Gaspar_StefanGaspar-Garu Stefan Gaspar_Stefan Data 12 noiembrie 2024 16:50:00
Problema Sortare topologica Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include<fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int a[5000][5000],d[50000],c[50000];
int n,i,j,m,x,y,u,p;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        a[x][y]=1;
        d[y]++;
    }
    u=1; p=1;
    for(i=1;i<=n;i++)
      if(d[i]==0)
      {
          c[u]=i;
          u++;
      }
    if(u==1)
    {
        c[u]=1;
        u++;
    }
    while(p<=u)
    {
        x=c[p];
        for(i=1;i<=n;i++)
            if(a[x][i]==1)
            {
                d[i]--;
                if(d[i]==0)
                {
                    c[u]=i;
                    u++;
                }
            }
        p++;
     }
    for(i=1;i<=n;i++)
        fout<<c[i]<<" ";
     return 0;
}