Cod sursa(job #601998)

Utilizator alinhAlin H alinh Data 8 iulie 2011 17:35:46
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <queue>


using namespace std;

ifstream fi;
ofstream fo;

unsigned short q,e;
unsigned short m,n;
unsigned short x1, x2;
queue<unsigned short> a[50001];
unsigned short k[50001];
queue<unsigned short> l;
queue<unsigned short> c;

int main()
{
    fi.open("sortaret.in");
    fi >> n >> m;
    for (int i=1; i<=n; i++)
        k[i] = 0;
    for (int i=1; i<=m; i++)
    {
        fi >> x1 >> x2;
        a[x1].push(x2);
        ++k[x2];
    }
    fi.close();

    for (int i=1; i<=n; i++)
        if (k[i] == 0)
        {
            c.push(i);
        }
    while (!c.empty())
    {
        q = c.front();
        c.pop();
        l.push(q);
        while (!a[q].empty())
        {
            e = a[q].front();
            a[q].pop();
            --k[e];
            if (k[e] == 0)
                c.push(e);
        }
    }

    fo.open("sortaret.out");
    while (!l.empty())
    {
        q = l.front();
        fo << q << " ";
        l.pop();
    }
    fo.close();
    return 0;
}