Cod sursa(job #2557437)

Utilizator ralucaantonAnton Raluca ralucaanton Data 25 februarie 2020 19:51:11
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int p[100005], v[100005], n, m, x;
struct nod { int et;
             nod *urm;
};
nod *L[100005];

void add_nod (int a, int b)
{
    nod *q;
    if(L[a]==NULL)
    {
        q = new nod;
        q->et = b;
        q->urm = NULL;
        L[a] = q;
    }
    else
    {
        q = new nod;
        q->et = b;
        q->urm = L[a];
        L[a] = q;
    }
}

int main()
{
    int i, j, k, ok;
    nod *q;
    fin >> n >> m;
    for(k=1; k<=m; k++)
    {
        fin >> i >> j;
        add_nod(i, j);   ///il pun pe j in lista lui i
        p[j]++;
    }
    k=0;
    for(i=1; i<=n; i++)
    {
        if(p[i]==0)
            v[++k] = i;
    }
    for(i=1; i<=n; i++)
    {
        x = v[i];
        q = L[x];
        while(q!=NULL)
        {
            p[q->et]--;
            if(p[q->et] == 0)
                v[++k] = q->et;
            q = q->urm;
        }
    }
    for(i=1; i<=k; i++)
        fout<<v[i]<<" ";

    fin.close();
    fout.close();
    return 0;
}

/*
    var 60pct
    ok=1; k=0;
    while(ok==1)
    {
        ok=0;
        for(i=1; i<=n; i++)
        {
            if(p[i]==0)
            {
                v[++k] = i;
                p[i]--;
                q = L[i];
                while(q!=NULL)
                {
                    p[ q->et ]--;
                    q = q->urm;
                }
                i = n+1;
            }
        }
        for(i=1; i<=n && ok==0; i++)
        {
            if(p[i]!=-1)
                ok=1;
        }
    }*/