Cod sursa(job #1974609)

Utilizator MaligMamaliga cu smantana Malig Data 28 aprilie 2017 09:29:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");

#define pb push_back
#define ll long long
const int NMax = 5e4 + 5;

int N,M;
int inDeg[NMax];
vector<int> v[NMax],sol;

int main() {
    in>>N>>M;
    for (int i=1;i<=M;++i) {
        int x,y;
        in>>x>>y;
        v[x].pb(y);
        ++inDeg[y];
    }

    queue<int> Q;
    for (int i=1;i<=N;++i) {
        if (!inDeg[i]) {
            Q.push(i);
        }
    }

    while (Q.size()) {
        int nod = Q.front();
        Q.pop();
        sol.pb(nod);

        for (int k=0;k < (int)v[nod].size();++k) {
            int next = v[nod][k];
            --inDeg[next];
            if (!inDeg[next]) {
                Q.push(next);
            }
        }
    }

    for (int k=0;k < (int)sol.size();++k) {
        out<<sol[k]<<' ';
    }

    in.close();out.close();
    return 0;
}