Cod sursa(job #601990)

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

#include <iostream>

using namespace std;

ifstream fi;
ofstream fo;

int m,n;
int x1, x2;
queue<int> a[50001];
int k[50001];

//queue<int> c;
queue<int> l;
queue<int> c;

void visit(int p)
{

}

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())
    {
        int q = c.front();
        c.pop();
        l.push(q);
        while (!a[q].empty())
        {
            int e = a[q].front();
            a[q].pop();
            --k[e];
            if (k[e] == 0)
                c.push(e);
        }
    }

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