Cod sursa(job #1106353)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 12 februarie 2014 18:54:33
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
# include <cstdio>
# include <vector>

using namespace std;

struct nod
{
    vector <int> vecini;
    int gradIn;
    bool sters;
};

const int N = 50000;

nod noduri [N + 1];
int n, m;

void citeste ()
{
    int n2;
    int n1;
    int i;

    scanf ("%d %d", & n, & m);

    for (i = 1; i <= m; i ++)
    {
        scanf ("%d %d", & n1, & n2);
        noduri [n1]. vecini. push_back (n2);
        noduri [n2]. gradIn ++;
    }
}

void init ()
{
    freopen ("sortaret.in", "r", stdin);
    freopen ("sortaret.out", "w", stdout);
    citeste ();
}

void stergeNod (int poz)
{
    int i;

    noduri [poz]. sters = true;

    for (i = 0; i < noduri [poz]. vecini. size (); i ++)
        noduri [noduri [poz]. vecini [i]]. gradIn --;
}

void rezolva ()
{
    int i;
    bool f = true;

    while (f)
    {
        f = false;

        for (i = 1; i <= n; i ++)
            if (noduri [i]. gradIn == 0 && ! noduri [i]. sters)
            {
                stergeNod (i);
                printf ("%d ", i);
                f = true;
            }
    }
}

int main ()
{
    init ();
    rezolva ();

    return 0;
}