Cod sursa(job #3255865)

Utilizator Gaspar_StefanGaspar-Garu Stefan Gaspar_Stefan Data 12 noiembrie 2024 16:43:22
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include<fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int a[50000][50000],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; //se creează matricea de adiacență
        d[y]++; //se reține gradul intern al nodului y
    }
    u=1; p=1;
    for(i=1;i<=n;i++)
      if(d[i]==0)
      {
          c[u]=i; //se adaugă la coadă nodurile care au gradul intern 0
          u++;
      }
    while(p<=u)
    {
        x=c[p];
        for(i=1;i<=n;i++)
            if(a[x][i]==1)
        {
            d[i]--; //dacă i este vecin al nodului x, se scade gradul său intern
            if(d[i]==0) //dacă gradul intern al nodului i se adăugă la coadă
            {
                c[u]=i;
                u++;
            }
        }
        p++;
     }
    for(i=1;i<=n;i++)
        fout<<c[i]<<" ";
     return 0;
}