Cod sursa(job #2070692)

Utilizator MaligMamaliga cu smantana Malig Data 19 noiembrie 2017 20:25:59
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>

#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif

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

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
const int NMax = 5e4 + 50;
const int sMax = 25e4 + 5;
typedef pair<int,int> point;

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

int main() {
    in>>N>>M;
    for (int i=1;i <= M;++i) {
        int x,y;
        in>>x>>y;

        v[x].pb(y);
        ++grad[y];
    }

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

    while (Q.size()) {
        int node = Q.front();
        Q.pop();

        for (int nxt : v[node]) {
            --grad[nxt];
            if (!grad[nxt]) {
                Q.push(nxt);
                out<<nxt<<' ';
            }
        }
    }

    return 0;
}