Cod sursa(job #3255863)

Utilizator Gaspar_StefanGaspar-Garu Stefan Gaspar_Stefan Data 12 noiembrie 2024 16:41:28
Problema Sortare topologica Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include<fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int a[1001][1001],d[1001],c[1001];
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++;
     }
     int gasit=0;
     for(i=1;i<=n;i++)
        if(d[i]>0)
            gasit=1;
     if(gasit==1)
        fout<<"graful are circuite";
     else
        for(i=1;i<=n;i++)
            fout<<c[i]<<" ";
     return 0;
}