Cod sursa(job #1610743)

Utilizator Vali_DeaconuVali Deaconu Vali_Deaconu Data 23 februarie 2016 18:32:44
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
# include <fstream>
# include <queue>
# include <bitset>
# define MAXN   50010
# define pb     push_back
using namespace std;

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

vector<int> L[MAXN];
queue<int> q;
int n, m, x, y, curent, vecin;
int gint[MAXN];

int main() {
    fin >> n >> m;
    for (int i=1; i<=m; ++i) {
        fin >> x >> y;
        ++gint[y];
        L[x].pb(y);
    }

    for (int i=1; i<=n; ++i)
        if (!gint[i])
            q.push(i);

    while (!q.empty()) {
        curent = q.front();
        q.pop();
        for (unsigned int i=0; i<L[curent].size(); ++i) {
            vecin = L[curent][i];

            gint[vecin]--;
            if (!gint[vecin])
                q.push(vecin);
        }
        fout << curent << " ";
    }

    return 0;
}