Cod sursa(job #1957153)

Utilizator MaligMamaliga cu smantana Malig Data 7 aprilie 2017 13:02:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

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

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].push_back(y);
        inDeg[y]++;
    }

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

    while (!Q.empty()) {
        int nod = Q.front();
        Q.pop();
        sol.push_back(nod);

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

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

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