Cod sursa(job #2273900)

Utilizator Monstergentleman35Ciopraga Razvan Monstergentleman35 Data 1 noiembrie 2018 09:38:24
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

struct Item
{
    Item *next;
    int val;
};

struct Lista
{
    Item *st,*cur;
};

int n,m,nod,i,a,b,nrplasat,st,sf;
bool ok;
Item *iaux;
Item *Elem;
Lista Adiac[50005];
int Grade[50005];
int Coada[50005];

void dfs(int);

int main()
{
    fin>>n>>m;
    for (i=1; i<=n; i++)
    {
        Adiac[i].st=new Item;
        Adiac[i].st->val=0;
        Adiac[i].st->next=0;
        Adiac[i].cur=Adiac[i].st;
    }
    while (m!=0)
    {
        m--;
        fin>>a>>b;
        Grade[b]++;
        Elem=new Item;
        Elem->val=b;
        Elem->next=0;
        Adiac[a].cur->next=Elem;
        Adiac[a].cur=Elem;
    }
    st=1;
    for (i=1;i<=n;i++)
     if (Grade[i]==0)
    {
     sf++;
     Coada[sf]=i;
    }
    while (st<=sf)
    {
     nod=Coada[st];
     fout<<nod<<" ";
     if (Adiac[nod].st->next!=NULL)
     {
      iaux=Adiac[nod].st->next;
      while (iaux!=NULL)
      {
       Grade[iaux->val]--;
       if (Grade[iaux->val]==0)
       {
        sf++;
        Coada[sf]=iaux->val;
       }
       iaux=iaux->next;
      }
     }
     st++;
    }
    return 0;
}